Definatly look for a host that will let you expand.
If you go dedicated ask how hard it would be to upgrade to a bigger server later.
If you go VPS ask how hard it would be to upgrade later so you have more resources.
If you decide on shared always ask the host first, as the last thing you want is for them to cut you off. You might find you have to pay more than you would like, but you MAY find a host that will do it.
I would say VPS would be best for now, if you can easily get more resources without downtime.
Note to self: Add something funny! Search is your friend!
You won't find a whole lot of them around WHT that don't want some type of control panel on the machine. Those that will work compeltely without a control panel are most likely going to be a bit costly.
You could always opt for DirectAdmin, I prefer it to CPanel and it's usually cheaper (I think it's $10/mo cheaper at Layered Tech). There is also the option of maybe a LiquidWeb manage VPS solution.