Have you looked into virtual private servers (VPS)? They sort of hit that sweet spot between shared and dedicated hosting, for significantly less cost than a dedicated server, often with better hardware and more ram for the cost, and you can slide up as your needs increase. I've been very happy with slicehost.com and would recommend them (they currently host this site).