wheel - 12:16 am on Jan 30, 2011 (gmt 0)
3 seconds on a T1 line sounds fine.
My guess is that you're getting slow response on the occassion when others are gobbling up server resources - though one would think hosts would have that under control.
Rather than a dedicated server, you might step your way into a virtual dedicated server. It's like shared hosting, but at the server level. Start there instead of actually getting a whole physical server (in fact, I suspect that these days virtual dedicated servers have many advantages of a physical dedicated server).