If you can find it Fort Collins Brewery has an "Out of the Ashes" series of beers that are all smoked. They are limited release so might be hard to find, but could give you some ideas. The smoked Marzen should still be on shelves and the smoked IPA is going to be released on June 13th.
I second the smoked porter idea given earlier. Although it may take some time to get good. I bottled mine back in Jan and it is just starting to get good. It was a heavy porter, 8.6% ABV, secondary on vanilla and oak chips. I used smoked malt, Weyermann, for 40% of my grain bill and wish I had used more.