I almost think that any solution that’s grid/shared is going to have it’s share of slowness. I’ve been with GoDaddy and with HostGator and in both cases I’ve experienced slowness. I know for a fact I’m going to end up leaving HostGator in the near future, but it’s just down to where to go.
My two biggest complaints with HostGator is the only real support I’ve been able to get is through their little web chat system instead of having a good option to call, and that you seem to be extremely limited on quite a few things. Like, you can never see a list of your domains – you just need to remember them all to know what you have and you can’t edit things like MX records. Someone at HostGator has to do it for you. I’d really rather have more control of stuff like that. Based on those two elements, it’d almost be worth it to just go back to GoDaddy and put up with their hosting back end that I’m not a huge fan of.
It seems to me like if you are going to go for MT, you might want to jump right into doing the VE or start with GS and intent to upgrade to VE. You really do get what you pay for it seems.