A while ago I wrote a custom bash tab completion plugin which would do CD path completion out of a couple of directories that I usually store interesting things, if there was no local completion. It worked fairly well, but the other night I realized that I'd probably be happier with something that did completion using the CDPATH.
Today I did some searching around and came across the bash-completion package on the Working more productively with bash 2.x page. Included there is an RPM which I installed. It was then as easy as sourcing "/etc/profile.d/bash_completion.sh" to get the completions set up. The next thing I knew I was able to complete via my CDPATH.
I also looked at zsh a bit, because it's well known for having good completion. I wasn't able to make any progress with it, though. I did test out the vi command-line editing mode, and found it was better than the editing available in bash 2.x. In particular, I had problems with "cwstring