Well, after an exhausting search. Um, okay, maybe 10 minutes.
I've gone with
http://www.aplushosting.com/
They seem pretty reliable, gave me all the options I wanted and more for 7 bucks a month.
Plus, how can you go wrong with a company that names all there servers and workstations after StarWars/StarTrek/Andromedia characters.
Thanks guys for the advice