Needs: network performance and costs, desperately.

I wouldn't mind SAN/non-local storage performance and costs too.

VM cost isn't where AWS gets you. It's ALLLLLLLL the other nickel and diming that they kill you on, especially since outbound data transfer costs a log of money to get off of the platform.