I second the idea of the alphabet going down the side. It's implemented on some [cough] Apple products we know, and it's sufficiently unobtrusive even in their relatively narrow portrait mode. Granted, they have more vertical room to lay out the alphabet, too, but I imagine it would work fine.
After all, N8x0 screens are as many pixels tall in landscape as those devices are in portrait (!).