My vote for a shuffle play option for playlists and radio stations. If you want to compete with Pandora, you must have this option. I'm using your free service right now, but I pay for the premium service from Pandora. I will not pay for your premium service, nor will I click any of your ads in the free version, until Spotify's many shortcomings are addressed.
You can use shuffle already for playlists by clicking the icon in the bottom right corner.
Bringing back the old radio features where you could combine radio stations has been suggested here:
Add your kudos there please! ;)