I recommend the Holux 236. It's smaller than the LD-1W, uses the same BL-5C battery as a lot of Nokias, and uses the SiRFStar III chipset for ultra fast satellite acquisition times. Plus, it's less than $80!
Be advised, the Nokia LD-3W also uses the SiRFStar III chipset and uses the same battery, but it's a little bigger and pricier.
If you want to go even smaller, check out the Holux 240.
I have no problems using my BT headset and BT GPS at the same time.
BTW, my wife uses a 6681, Holux 236, and Tom Tom v5 for navigating.