I am about to go wireless at my 3500+sq ft home. I have a new HP laptop. What type of router will I need to get the adequate coverage in my entire house?

According to the 802.11x protocol sheet. The following is the layout of the protocols and their affective ranges.

Standard-Indoor-Outdoor
802.11a-115ft-320ft
802.11b-125ft-460ft
802.11g-125ft-460ft
802.11n-230ft-820ft

These ranges vary greatly depending on a lot of things. Obviosuly obstacles within the house, ie: walls, stairs, doors, intereference from devices on the same frequency/bandwidth, etc...

What type of internet do you have? Cable or DSL? Do you have multiple access jacks for these internet connections!

If you are having trouble with one wireless computer which is far away from the router you can get usb wifi adapters with built in directional panel antennas of pretty much any size. Check out the SuperPass 2.4 GHz 34dBm Panel USB Antenna 802.11b/g/n on eBay.