Wow, I’m surprised this has never cropped up before… (-:
The eternal Canon / Nikon debate boils down to personal preference. Play with a few in a shop and see what clicks with you.
The 500D is a good camera but not particularly new, so there may be decent second hand deals to be had.
Define “lenses”; most bodies are available with a fair-to-middling general purpose ‘kit’ lens, but what you need after that would depend what you’re doing with it.
Sarcasm aside, we’ve discussed this many times; search the forum for dSLR, there’s a lot of good advice to be had.