I lived in Nara, near Nara-koen for four months, so I just had to put my two cents in. ^_^; The temples on Sanjo-dori are surrounded by modern buildings, but are incredibly elegant and definitely worth a look. Also, Nigatsu-do above
Todai-ji affords an excellent view of the city and temples spread out below, and there is a lovely shady path leading down from the temple through the Park (which is something wonderful in its own right-- the trees are amazingly huge and beautiful.)
Kyoto, depending on where you look, has a lot to offer as well. The area near Yasaka Shrine and Kiyomizu-dera is filled with older, more traditional architecture, and bumps into Gion. Sannen-zaka, just on the other side of Yasaka, is filled with interesting shops, many of which sell traditional pottery and other art (although it's terribly expensive, it's worth seeing.) The hills outside Kyoto are full of temples, and you can usually find a bus to take you to the right one, although it's a bit of a ride. Sanzen-in, past Mt. Hiei, is particularly beautiful and there's enough inside the complex (gardens, buildings, views) to keep you exploring for at least half a day. Gansen-ji, in the hills between Nara and Kyoto, is at the end of a short hiking trail that takes you past several Buddhist images carved in rock faces on the hillsides. It's especially enjoyable in the fall, and even then there aren't usually lots of tourists.
That's probably quite enough from me. I could go on for ages.
Hope it helped!
Eli