I was in Kyoto for less time than Tokyo. At first, it seemed like a sleepy and flat city, but after we found the right areas it came to life with a romantic charm that you could never find in Tokyo.
Specifically there's a lot going on at the Geisha district, and there's a street called Pontocho street along the river that has some excellent restaurants. I also found a place called Sake Yoramu, which is a sake bar owned by an Israeli, so he could speak english and serve us excellent sake. One he gave us was ~30 years old!
Official Kyoto cuisine is the Kaiseki, a multi-course meal. When you're going, there will probably be a lot of one particular seasonal food served (I went in April, which was Bamboo). In general, the kyoto food is visually pleasing but more bland (cough nuanced...) than what you'll find in Tokyo.
The way to stay in Kyoto is in "ryokan," which is a traditional style inn. They'll serve kaiseki in your room and give you a kimono to wear for the night. There's a few sites online that will help you find ryokan to stay in and will also indicate if it is a bilingual staff. Avoid one called Hiiragiya; it is universally called the best ryokan in Kyoto, but for $600 is really just a ripoff. Nonetheless, staying in this style will give you one of the most authentic japanese experiences.
Kyoto is littered with shrines and temples. Literally, you can't walk anywhere without bumping into one. If you only go to one shrine, go to the Fushimi Inari shrine. It has thousands of Tori (red gates) that you walk through on a path. It goes on for miles, and is a beautiful hike. You can also see the whole city from one of the stopping points (but not the peak, that goes even further!). There are little restaurant shops along the way, try eating at one of them. If you only go to two, also visit the Kiyomizudera temple, which is perhaps the most iconic temple with its waterfalls. There's also the Heian shrine (which is a 2/3 facsimile of a chinese shrine) and the Ginkaku temple (aka Golden Pagoda).
A local once told me his favorite temple was Nanzen-ji, so I checked that out. I can't say it was too different, but if you walk around the grounds you'll discover a very out of place Roman aqueduct. Following this further east is a small an quiet hike to another few secluded buddhist temples and was worth the whimsical outing.
Nijo castle was okay, if you do go make sure to head to the tea house for some green tea and mochi.
Matcha is clearly the flavor of choice in Kyoto. There are many cafes that are dedicated to desserts, ice cream, and matcha flavored drinks. I found some great treats at Kyouhayashiya, but I'd imagine there are many other places to go. If you need a tranquil spot for a latte and doing some work, KissaMaster's garden views will fit the bill (and you can even purchase leather backpacks there!).
There's also a few outdoor shopping centers, which were kind of fun.