@Rav: I don't really know verizon since I'm in Canada, but if it's a GSM network they've got, then it should work. But I'm guessing they don't do GSM...
Anyways, I'd suggest T-mobile, because the phone has the 3G frequencies for T-Mobile.. if you're on AT&T, you'll only get edge!
Have a look at this : http://www.amazon.com/Nokia-N900-Unlocked-Computer-Touchscreen/dp/B002OB49SW
it explains it correctly.
About how long it took, it took about 1 hour, on and off... that's the beauty of it.. it was just a svn checkout from scratchbox (the SDK), then 'make' just like on any linux machine... unfortunately, ORP's makefile is crap, so it had to download and compile 11 dependencies (zlib, libpng, freetype, curl, faad2, SDL, ffmpeg, openssl, wxWidgets, etc..) although most of them already come by default with the N900 (faad2 and wxWidgets toolkit doesn't)..
I had some issues with compiling some of the dependencies (some errors in the code itself), and it also had some conflict issues between the dependencies compiled by ORP and the ones installed by default on the system.. but once I fixed all that, it was just a matter of 'make', and overall it took me about one hour of work with most of that waiting for compilation to finish.