I've done karaoke... much to the dismay of anyone who's heard me.

I try to not do karaoke as most of the venues charge for it, have age restrictions, and/or other things that make it only possible for some folks to go do it.
The best place I've had karaoke is on Sunday nights at a bar named Wicked Willy's. The karaoke is free and your first song you sing nets you a free beer.
I live and work in NYC, so I know of a number of places.