Can anyone recommend color schemes other than Solarized that have extensive support across board (not only vim, but all the plethora of terminal emulators, command-line applications, etc.)?

Solarized is too low-contrast for me, so I have hacked-on support for hybrid (solarized syntaxes + tommorow color codes), but it's not really uniform. And, imho, well-balanced contrast is the most important thing.

Non-exhaustive list of applications that I'd like to see supported - vim, emacs, tmux, weechat, vifm, newsbeuter, taskwarrior, mutt...

There is a related project called Base16-Builder: https://github.com/chriskempson/base16-builder

With Base16-Builder you can make a Yaml file of colours and it will build profiles for a zillion apps. It's pretty easy to hack to build other profiles as you just need to make an erb.

Base16 is organized in pretty much the same way as Solarized colours, so if you have gotten used to Solarized and just want to adjust the colours to something easier to see (I suffer from the same problem you do), then I think it is the way to go.

I hesitate to mention this because it isn't quite ready yet, but where I work we do a lot of remote pair programming over tmux. The problem is that everybody has their own idea of what colours look good. My buddy and I made a vim colorscheme that looks reasonable with many different palettes, called agnostic: https://github.com/ygt-mikekchar/agnostic

So if you ever need to pair program over tmux and one person wants a light background, but another person wants a dark backgroun, you can do it it. If you do that kind of thing a lot, then I recommend working with agnostic. Otherwise I think Base16 is probably the way to go.