Putting it all together
If you've made it this far, you may be more confused than when you started, given all the options available. So let's see if I can boil it all down to a few basic points:
Understand the problem
Now that you know how radio waves travel, look for obvious problems from metal, interference sources, and high water-content items. Eliminate the problems you find if you can, and move stuff around if you can't. Relocation is the cheapest tool you have in improving wireless LAN performance.
Less may be more
If relocation doesn't get you what you need, resist the urge to throw the kitchen sink at the problem. You'll have better results if you use only as much improvement as you need, and your wallet will stay fatter, too!
Keep it simple
Higher-gain omnidirectional antennas are probably the simplest, most cost-effective improvement you can make, especially when used at the Access Point. If your AP has two antennas, make sure you upgrade both with the same make and model. If that doesn't get you what you need, try upgrading clients that are still giving you trouble.
Don't fear expansion APs
With the alternative methods of HPNA and HomePlug available, adding on access points doesn't necessarily mean fishing cables through walls. Sometimes just one additional, properly placed access point is all that's needed to fix what ails you, and the cost can end up being lower than you think.
So don't just complain about your wireless LAN's problems... now you can do something about them!
For Further Reading
[1] Michael Young's Radio Primer whitepaper has a more detailed description of the radio-as-light analogy
[2] Trevor Marshall's Antennas Enhance WLAN Security article is a very readable overview of how antennas can solve both performance and security issues for wireless LANs.