I don't think i'd go with adding black bars, that totally defeats the purpose. If someone has a nice widescreen display resolution, they *want to use it* fully, they aren't going to choose a widescreen mode only to have you chop off a large percentage and not use it.
Now you're arguing at cross purposes with yourself. You can't do everything you said about keeping the display 100% consistent across resolutions without having black bars. If you choose not to have black bars, you're going to be scaling things differently or leaving gaps at some resolutions and not in others.