The g/f and I took out an '02 Altima SE and I agree that it's a great car. My biggest complaints were with the dash and the air vents. The dash was sort of hokey looking and just didn't work with the car. The airvents were small, hard to reach, and felt cheap. Besides those though, it was a solid car. Unparalleled seating space for its class, unmatched power, and pretty sharp looking from the outside.
One warning though - you said you wanted leather. Well, to get leather you have to get a couple other options and once you start tacking on a bunch of options, the price skyrockets up to close to 29k. Factor in TT&L and the car is now $30,000.
You may actually wind up getting a better deal with the options you want with a Maxima. The Altimas are the hot items on the Nissan lots and dealers are having problems getting rid of the Maximas.
Basic difference between the Maxima and altima are the following
More power on Maxima. 255 vs 240 in the altima
Available 6 speed manual on the Max (don't know if they are shipping yet though)
Max is a longer car