If they don't support those things, what makes you think they will support cgi? They may support it, but only their preconfigured scripts.
$16.95 a month will get you a quality host that will support almost everything under the sun including a shopping cart, give you tons of space, a huge traffic quota, and a bucketload of POP email accounts. $24.95 will get you even more........check out the options. It's Apache on *ix.
http://www.webaxxs.com/whostSE2.html