cPanel, WHMCS, and Softaculous will do exactly what you want to do, aside from the advertising space. There are really no good solutions out there (outside of custom scripts) for placing ads on user pages. Do a search here and you might find some (i.e. iPanel), but they are largely buggy and unsupported.
As far as the right server, how many free accounts (I'm guessing you're getting into the free hosting business) do you plan to provide? For starts, a reseller account (be careful, as many hosts do not allow their resellers to operate free hosts, as they are normally far more prone to abuse) or VPS might work, with a dedicated server after your host starts to grow.
A good reseller account will probably run you $10 and up, a VPS slightly more than that, and a good dedicated server $150+. Of course you also have to factor in the license costs. Softaculous, cPanel, and WHMCS all cost money.