How about the Hotel Seiyo Ginza?

Mr. Megatop and I stayed there last December on our first trip to Japan. It's a long walk or short cab from Tokyo Station, where the Narita Express arrives and the Shinkansen (bullet trains) depart. On the edge of Ginza, it's naturally close to that main shopping district. Ginza-itchome Station on the Yarukucho Line is a stone's throw away, and Ginza Station (where the Ginza, Hibiya, and Marunouchi lines cross) is maybe five blocks. As you noted, from the subway you can get to just about anywhere. The fish market is maybe a dozen blocks away from the Seiyo Ginza, andthe main Kabuki theater is on the way there. The Imperial Palace is a walkable too (in the other direction), though it's a bit of a hike. If you've made it that far, Yasukuni Shrine and War Museum is another reasonable walk. Lots of good and great restaurants in Ginza, though some are expensive.

Mr. Megatop and I had a very nice room with a King Bed. It qualified as luxury, though was a bit dated. We found a good rate in your budget range. The Seiyo Ginza is often recognized as having one of the best concierges in the world. They were good, but I don't know about THAT good. The doorman, however, was one of the best I've ever had--he greeted us by name when we arrived in a cab without us introducing ourselves (he knew who was checking in that morning or he checked the tags on our luggage or both). And he was a hunk too!