With P4 servers so cheap as the trend seems to be going towards dual core you can pick up a nice P4 for cheap. We started out years ago on a Celeron based server with a gig of ram and a 7200rpm IDE hard drive. We had about 15 sites on this server. This server had cPanel installed which did tag the Celeron quite a bit.
Start with a P4? You dont have to even go as powerful as a Celeron. If you want to start out strong, but not too expensive, you can find a decent colo company for under $80/monthly and for example, a dual pIII server.