I decompiled the Spotify APK (latest version from my S4) and removed any android:screenOrientation="portrait" attributes from the AndroidManifest.xml file. It now shows up in the correct orientation for me. I used an attached keyboard/mouse to login, but after that I've just been using the Amazon remote to click through things on my playlists (on some of the screens, it helps to push the the left before scrolling up or down). If you hit the search box, the on screen keyboard shows up... so while it's not perfect, I think you can get by with the standard remote.
I've posted a build here if you want to try it:
httttp://d-h.st/Lel