So I did some research and prepared to fix all the problems at once. Below are the steps I followed.
DISCLAIMER: I AM NOT RESPONSIBLE FOR ANY DAMAGE YOU MAY DO TO YOUR PHONE FOLLOWING THESE STEPS. DO IT ON YOUR OWN RISK!
Step 1: Unlock the bootloader
Warning #1: This procedure may void your warranty!
Warning #2: During this procedure the phone will be reset to the factory state, so backup all your data!
You have to register at HTCDev.com, and follow the procedure described there. Download their fastboot utility, use it do get your device identification code, submit that, and HTC emails you the unlock code, which needs to be flashed to the device.
Step 2: Flash recovery ROM
Download ClockworkMod recovery (get the Superuser application there as well - it's under the Download ROMs link). Reboot the phone into FastBoot mode by holding the Volume-Down button while switching it on. Connect to USB and use the following command to flash the recovery ROM:
fastboot flash recovery recovery-clockwork-18.104.22.168-ville.img
More details about flashing, working with ROMs and other hacking stuff could be found at XDA-developers.com. It's an excellent resource with a lot of useful information, which helps to get maximum from your phone.
Step 2a: Make a backup
Reboot the phone to FastBoot mode again. Select the Recovery menu item using Volume-Up/Down and Power buttons. When in the Recovery mode, select Backup/Restore and make a Nandroid backup just in case.
Step 3: Root the phone
Reboot the phone normally, connect it as USB storage, copy the Superuser su*.zip file there. Reboot to recovery mode, flash the file using "install zip from sdcard" menu, and reboot again. The phone is now rooted!
Step 4: Fix the menu button
Download the Menu_Mod.zip file from this post at XDA-developers and flash it the same way in Recovery mode. The thread has some details on what exactly is done by flashing that file. There are different versions of the mod for different versions of the phones. The one above is specifically for the T-Mobile version as mentioned in the post. The change assigns the menu action to the Task Switcher button, and the task switching action to the long-press on the Home button as was on the older phones. It works beautifully!
Step 5: Removing the bloatware
There are options how to do this, but all of them require root access - that's why we needed the Superuser utility. A good way is to use Titanium Backup, which allows to backup an app before uninstalling it - just so it could be restored later if required. The list of the apps, which are not really needed is discussed here. I removed 24 applications! That's how much useless junk was there. And that's not counting those I kept just in case (may get rid of them later).
Step 6: Fix the multitasking issue
Apparently the parameters, which control the behavior of the system task manager, are editable (with root access of course), and their tweaking might help. Install MinFreeManager from Google Play. Here is a good article on the subject. The idea is to let the background applications run, do not kill them. Looks like that reducing the numbers in that utility from default values, especially for the Hidden App, helps the applications stay in memory longer, so switching back to them can be done without their restarting and reloading. I noticed a great improvement, though I guess removing of the useless junk, which took memory, helped here as well.
* * *
Now after doing all this, and reinstalling my usual set of applications, I see about twice more of the available memory (normal idle numbers were around 130-140MB, now they are up to 250-280MB and even more). Everything seems to be working as it should, the phone not only looks great, but now works well too. I am happy! :)