A place I've often gone is Chibo, the okonomiyaki place at Yebisu Garden Plaza at the top of the large building there.  It's part of a chain. It's probably not the best okonomiyaki but it's not bad and the view is great from the 37th floor.

Especially if you are from out of town you might want to check it out since you get both the view and you get to try something new.