So, with that in mind:

1) Where does one go shopping to buy a barbecue grill? I see them at the hardware stores, but I'm not sure if that's our best option.
2) We'd like something small, but not "disposable" -- we could just go buy a temporary grill for $12 from the local Walmart, but we'd really like something a little better than that ;)
3) Is there such a thing as a grill that can do both gas and charcoal? I personally vastly prefer charcoal grilling to gas, but all the grills we've looked at have been gas. I know, I know, carcinogens, but I still prefer charcoal.
4) Any brand or specific model recommendations?

1) Hardware stores, fireplace stores, Home Depot, Lowes, WalMart, Amazon, etc.

2) The $12 grill will last as long as you are thinking - not long at all. :-)

3) Yes, but they either aren't very good or cost a fortune. Like most things, the one-trick ponies work far better than the all-in-one solutions.

4) Yes, without hesitation, the venerable Weber kettle is the way to go for you. You prefer charcoal, you want the price reasonably low, you want quality and you want a small size. The 18-1/2" model would work well. You can get version with the ash-catcher for about $120, and the basic model is only about $65. Or you could just get the little Smoky Joe portable for about $30. Weber quality is outstanding, as is their customer support, and their products are built in the US supporting good jobs for thousands.

You might want to take a look at this too:
http://bbq.about.com/od/charcoalgrills/tp/aatp062604a.htm

When I bought my house I found I grill out a lot more if I have a gas grill sitting there and don't have to cart charcoal and ashes. I bought a Char Broil Quickset at an end of season sale for $120. Great buy, and it works fine for me. Just remember to preheat it. Mine has a side burner, so I keep whatever sauce I am using hot. I grill a lot of vegetables although I am a meat eater. Nothing beats a portobello mushroom brushed with oil, sprinkled with some thyme and salt, and grilled. Oh, boy. And don't forget the eggplant. Slice the eggplant and slather it with barbecue sauce while it grills.

Good luck, hope this helps.