I switched to urxvt (rxvt-unicode-256color) after I switched to UTF8 (and wterm and aterm couldn't handle it). Right now, it's probably the best terminal in terms of features and compatibility.
And I can't absolutely imagine anything rewritten to only come near it within 5 years.
Try this: Use utf8; ssh to some host and start Midnight Commander, Do all characters and line-characters look right? Do all keyboard-shortcuts work? Does clicking with the mouse on menu-items work? If not, your terminal is trash and totally unuseable.
Start mutt, read your spamfolder, can you see russian and chinese characters in the spam or are there garbled characters? If garbled, either your terminal is broken or misconfigured.
Now, try w3m (w3m-img) locally. Where are the images displayed? If they're not inline, you've still got some work to do.