I use Putty mainly to interact with my Ubuntu vm-boxen so I do spend some time getting the visual configuration correct. Basically, I set the font to MS Gothic, 9pt (for monospaced and Japanese), UTF-8 for received data, and terminal-type string to xterm-256color. I leave most of the Terminal settings alone because the defaults seem to work well.
On the Ubuntu side, I set LANG=en_US.UTF-8, aptitude install ncurses-term for additional terms. I check the terminal colorness via a nice script, and double check within a GNU Screen session and GNU Emacs (M-x list-colors-display). GNU Screen is not compiled with 256 color option so i re-compile it. I check the language by using Emacs (M-x view-hello-file) and also tig a git directory with i18n utf-8 log commits.
Unfortunately I still do get the weird "lqqqqk" thing on aptitude (line art missing?) but the spacing is still correct. Also pressing backspace in aptitude does a character insert, which I still have not conquered. Also I tested your command line w3m on my system and it looks nice. I rather use w3m from emacs, tho. :-)
Truth be told, I use a Japanese fork of Putty called Gottani (PuTTY ごった煮版) that helps more with Japanese but I think its pretty close to the normal Putty.
Aside: I also set Terminal > Features > Disable remote-controlled terminal resizing because `GNU Screen" overrides my window size setting.
All of the above is tested on Ubuntu 8.04 LTS "Hardy Heron".