I think you're on the right track with the vertical nav, it's especially comfortable in tablet+portrait mode, since your thumb can easily reach the buttons.
We've been testing someting similar (very early beta version), with very positive feedback from users: