The earliest ones for home users were the late model P4's I believe.
As for software, 99% will work flawlessly, as the OS handles the 32->64 conversion. That being said, all drivers MUST be 64-bit, so lack of device drivers can cause problems. (Example: The retail version of Splinter Cell:Chaos Theory will not run because the drivers for the copy protection are 32-bit, although the game itself works fine).
At this stage, unless you are running really old hardware, 64-bit is the way to go.
I should make a quick note: As of Vista, all 16-bit apps will not run in windows, regardless of what version you use.