Similar flavors to caffeine?
Caffeine is definitely bitter. About the only thing I know of that can add bitterness or that strong flavor to coffee is roasted chicory. It's a key ingredient in French Market coffee blends, and it makes them taste pretty darn strong, even though they have less caffeine.

You can get roasted chicory by itself at some supermarkets so you can add it to your decaf coffee, but it may be hard to come by in your area. If you can't find that, see if there's a decaf French Market blend. That'll have chicory and may give you back the bitterness you crave.

I think you're probably out of luck on the tea, though. You might just cut well back on the tea and drink regular tea once in a while. A jolt of caffeine now and again won't kill you, and life's too short to drink tasteless tea.