It sounds like you went to Wal-Mart or something. If you're going to shop for head units, Wal-Mart (K-Mart, Shopco, et al) is the wrong place to go. Try Best Buy, or better yet, go to a shop that specializes in car audio. You'll get a better deal and a better product.
Circuit City sucks to put it plainly...Try an audio shop or even Best Buy is better than circuit city (but not by much) I just bought an Aiwa unit that has aux input. All Aiwa Units have this feature. The head is a pretty nice unit in my opinion and i like the quality i get out of it. almost all the units also have at least one set of preamp outputs.
In response to the post about kenwood head units, I have one (a KDC-3011) and I called about the aux input adapters, unfourtunatly for me, I was told that they only work on the high end eXcelon models.
I believe that the only decent decks around that will let you use AUX input are the JVC, Panasonic, Pioneer and Blaupunkt.. all others need to have a CD changer connected as well.. correct me if I'm wrong, but I don't think I am..