I'd like to single-step through the code displayed in a vim editor window, with all the power of vim to navigate it, plus commands to single-step, watch variables, set breakpoints, etc. tmux or screen can't give me that, nor can gdb -tui.

I was looking for the same thing, ended up using ddd, has watches, breakpoints etc. If you've found a better solution than that though feel free to let me know.

For everything except the data structure graphs, I prefer gdb's -tui option (split-screen code and "(gdb)" prompt) over ddd.

One feature I can think of jumping to line numbers which come from make or compiler errors.

Vim has that with its quickfix window.

For live debugging there's still a need for some way of getting the source locations you're interested in into that quickfix window. Not that there aren't probably plugins &c that do just that, but it doesn't fall out as straightforwardly as parsing build errors.