Ubuntu, Debian, Slax, and openSUSE have all had trouble with my LinkSys WMP54G wireless card, as well as the 2Wire USB device AT&T gave me when they hooked up U-Verse.
I've been hesitant to buy anything until I have some general idea that it will work relatively easily.
However, most of the USB cards I have looked up appear to have some issues, or require the use of ndiswrapper (which I would like to avoid, if at all possible).
What wireless cards have you used?