Things to do in Tokyo

I spend a light of time Kansai, Kyoto, Osaka, and sometimes Kobe. I live in U.S. Most of the year, but I will be in Tokyo the first week of December and honestly have rarely been there, except the airport. I am looking for recommendations for sights to see near Shinjuku or elsewhere. Also, I am interested in nightlife, but not Roppongi. I speak reasonable Japanese (not great), and I am not against meeting people, but I don't want to just be hanging out with other Westerners. I am a 40 yr. old Horitsu no Kyouju/Bengoshi, but a bit of a gym freak and in good shape so don't mind walking far to find good places. Not into clubs unless really good rock music.

Kabuki-cho is the place to go at night. Golden-gai street is the unique place for drinking. It's right behind BestWestern Shinjuku.

http://www.att-japan.net/modules/tinyd0/rewrite/tc_34.html

Meiji-Jingu (one of the largest shrine in mid town) is the place to walk from your hotel. It's between Shinjuku and Shibuya.

You could buy a guidebook and find out what really interest YOU. There are thousands of things to do in Tokyo...including just walking around in all sorts of neighbourhoods..

As Jay Key said, Golden Gai is worthwhile visiting. Here's a map of the area http://www.goldengai.net/shop/
I'd recommend Albatross, which is in the area marked as E on the map. Click on E and you'll see it on the right hand side, アル バトロスG. I think there is a rock-themed bar in one of the earlier lanes too. It's a fun area to wander around looking for a potential drinking hole. Be mindful that some places have high cover charges (look at signs outside) and some allow members only.

Omoide Yokocho is nearby too, and has an array of tasty yakitori restaurants. http://www.shinjuku-omoide.com/shop/map.html

Enjoy :)

The OP likes to walk....so do I...not being interested in bars at all I just walk...
One walk went from from Akasuka to Ueno park then to Yanaka, where I took the Yamanote to Otsuka--near Ikebukuro-- where I took the Arakawa tram line to some point outside the Yamanote llop line, going towards the terminus at Minowabashi.
Then back to the Yamanote..

One could go all the way to Kumanomae, the station where the tram line meets the elevated automated Nippori-Toneri liner, taking it back to the Yamanote line at Nishi-Nippori.