What's your "threshold of pain" as far as speaker size is concerned? From my experience, and from what I've read during my own research, you really can't go too small without sacrificing sound quality. That's one reason why the Bose cubes are bashed so often. Its my understanding that speakers with a main driver less than 4.5 to 5" aren't able to reproduce the "low-mid" frequencies. If you set the cross-over for your sub too high, its sound becomes too localized.
Luckily, there are lots of great options available. There are a lot of lesser-known brands of speakers that sound great, look great, and won't break your budget. As MARK_AR mentioned, hometheaterspot is a great site to start your research. I've been very happy with my Athena speakers. Their new Audition series looks pretty sweet, and they put out great sound without overwhelming a room's decor or costing an arm+leg.
If your budget must also account for a receiver, here's a couple of recomendations. I'm a big fan of Pioneer and Onkyo receivers. It looks like Pioneer has released this year's model, the VSXx16 models. the VSX816 is a really nice receiver that should complement your budget nicely. And, if you shop around, you might be able to find last year's stuff on clearance (the VSXx15 line up). If you can find a VSX-1015TX that fits your budget, that is a GREAT receiver at any price. Also, check out the Onkyo website. They have an online store that sells new, factory refurb and clearance stuff at great prices, with free shipping, too! The TXSR504 (or last year's model, the TXSR503) are an amazing value.
Also, SVS makes amazing subs, but if you need a receiver, they may stretch your budget. Hsu makes some incredible subs, too. Their STF-2 could fit nicely in your budget. I'll also thrown in a vote for my sub, a Velodyne DSP10, if you can find a good price on it. For a sub on a tight budget, it is hard to beat the Dayton Audio subs from partsexpress.com
So... find out how big a speaker you wife will sign off on, firm up your budget, make sure you account for all the equipement, then go shopping. I think with your budget and a little research online, you can put together an very sweet sound system that will really enhance the HD experience from your 622 (and will sound worlds better than a Bose system at 2 or 3 times the price).
good luck!