if you're coming from the point and shoot world, and think you'll stay pretty close to it, i'd say the d40. its the most user friendly for people who know p&s cameras.
the downside of that is a lot of the features are buried in the menus. if you dont see yourself switching back and forth between different iso, quality, white balance etc settings, then the d40 would be fine. if you want to get older non-digital oriented lenses (i just picked up 3 this weekend for $50 total ;D) then you'll want at least the d50 (d70 isn't worth the price bump imo). i'll probably be going to the d200 or d300 sooner or later just because more features/options are outside the camera instead of in menus.
i often want to switch between say spot metering (best for shooting models) to matrix metering (best for a whole scene) and back again, and would like to be able to you my pinky to do it with the flip of a switch. if things like that wouldnt matter to you, i'd say d40.
as for lenses, the 18-55 isn't bad, and you can get them cheap. get one with the lowest 'f' number you can get. a lower number means higher shutter speeds, which means less shots lost to camera shake and moving subjects. when i went from the f3.5-5.6 lens to the constant f2.8, the difference was AMAZING. but if you dont want a lens that's $500 or more, i'd go with the regular 18-55 kit lens. that is unless you plan to shoot a lot of outdoor events, then i'd get the nikon 55-200mm VR (vibration reduction. i'll sell you mine
as for nikon vs canon, i see it as mostly a build quality thing. nikons cameras seem to be more durable/sturdy to me. go pick up a nikon at the store and a canon of comparable price. and i've read some reviews of the cheaper canon lenses falling apart etc, whereas i've never heard anything of the sort with nikon (nikkor) lenses.
other than that, apparently nikon is better about keeping its lenses compatible with more of its cameras, canon reportedly 'updates' things and outdates their old lenses.
insaneboy also feels that the actual image itself coming out of nikons is nicer than canons. 'too much contrast' he says.
redline, what do you mean the 6mp d40 shoots like a 8.5-9mp? maybe i'm missing what you're trying to say but pixels are pixels....