Software for Ecommerce

I have experience with Shopsite ecommerce software and some custom ecommerce solutions. But now I am being invited to help develop a whole new internet and mail order business. It's a new company and they need an affordable structure.
I know that shopsite as other out of the shelf solutions are somehow limited, but they are still very good and affordable.
Do you guys have any suggestions of other similar (better, cheaper, ?) products?
My server's cPanel also offers Interchange shopping cart and Agora shopping cart solution, but I have no experience or knowledge about them. Do you?
Any ideas?
Thanks a lot.

I recommend OS Commerce.. it's a very good open source program.

Miva is very good but only because of the add ons (modules) supplied by third parties. These are sold at very reasonable prices, are excellent and allow you to overcome the enfuriating shortcomings with standard Miva. If you look at Miva, an essential module to buy is OpenUI (about $40) which overcomes most of Mivas shortcomings, including SEO. Miva has a very large user base. This has many advantages. It is solid, in my experience and also there are third party add-ons to allow direct import and export of data to and from Quickbooks (eliminating double keyting and all the mistakes that go along with that).

Can OS Commerce be altered and used in connection with Mod_rewrite so it makes pages look more SE friendly?