Get a Nikon D3100 with the kit lens, add maybe a 35mm f/1.8DX fixed focal lens and you're all set, those should be around $600-700 total and excellent to start out with. The next option up would be the Nikon D7000 which is spectacular in every way, but will cost about twice as much.

The major differences between Nikon and Canon are ergonomics, so go try both and see which you prefer, both make excellent and very equal cameras. Also Nikon's kit lenses tend to be way better than Canon's.