As everyone before has said, look at the lenses first; performance differences between the cheapest entry-level lenses and mid-level lenses seem to be far greater than performance differences in affordable DSLR bodies, and the bodies are likely to have a shorter life-span. However, many of the camera maker's DSLR kit lenses seem fairly decent, like the Nikon 18-70 f/3.5-4.5; the one that has raised most red flags is the Canon 18-55 f/3.5-5.6 (in both versions).
For example consider Phil Askey's recent review of the 350D at DPReview. Camera body highly recommended; kit lens more or less vetoed in favor of the 17-85 f/4-5.6. Askey declined to use the 18-55 kit lens for any of the shots in his sample gallery, saying it would misrepresent the capabilites of the body. The 17-85 raises the price of body plus one lens to fill your $1500 budget.
I have to throw in some options outside the Big Two; the Olympus E-300 with two lens kit of 14-45 f/3.5-5.6 plus 40-150 f/3.5-4.5 costs only as much as the 350D body alone, $600 short of your budget, and those kit lenses seems to have fairly good optical performance. With your budget you could upgrade that kit by replacing one of the two lenses by the 14-54 f/2.8-3.5 or the 50-200 f/2.8-3.5. Or get the E-1 with 14-54 f/2.8-3.5.