We managed to improve site performance by:

Fix indexing tasks that were hanging due to table errors (duplicate records, etc) - Status: Done
1. database backup (command line or phpMyAdmin found at https://hostname/phpMyAdmin)
2. find core_url_rewrite, then empty table (use phpMyAdmin)
3. delete var/cache (ssh)
4. reindex catalog index rewrites in index management (magento Admin panel in System|Index Mangm.)

(this is a solution found in http://www.magentocommerce.com/boards/viewthread/9342/)

Check for anomalies in page request (skin/theme, apache issues etc) - Status: Pending
1. Theme is requesting non-existing img files, e.g.: shirts.jpg which could not be located and appear to be a sample record populated by the theme (apache error.log). Status: Pending
2. Change default template back to blank (default) in Admin panel System|Configuration|General|Design|Themes|Default. It was looking for template and structure files in BLS theme (test theme). Status: Done
3. Enabled system profile in System|Configuration|Advanced|Developer|Debug|Profiler (set to yes). This was not enough to display full profiler data (it only shows time and global memory allocation (malloc)), so I had to enable it manually by editing index.php in the root dir (apachefilepath/magento/index.php) and uncommenting the line Varien_Profiler::enable(); (as recommended in http://www.magentocommerce.com/boards/viewthread/624/) I also enabled (uncommented) ini_set('display_errors', 1); These two should be put back to normal (commented) once tune-up is finished Status: Done
System resources - Status: Done
1. Memory seems to be running low, which is a good sign since it will simply take to upgrade the virtual machine in the Rackspacecloud server management and that will definitely improve server performance. (Currently running 256 ram) Upgraded to 512 on Oct 25-2010. System is running a lot better although we still might be a tad short for going live. We'll have to monitor after launch.
2. CPU seem fine
System tools - Status: Pending
(as recommended in http://www.magentocommerce.com/blog/comments/performance-is-key-notes-on-magentos-performance/).
1. Updates on the main packages (apache, php, mysql with aptitude safe-upgrade) showed already some improvement in page response and memory but some requests are still very slow (+9 secs). Status: Done
2. Install a PHP opcode cache such as APC or XCache. These can deliver significant improvements to PHP's responsiveness by caching PHP code in an intermediate bytecode format, which saves the interpreter from recompiling the PHP code for each and every request. (Followed instructions from here. Standar apt-get install package http://xcache.lighttpd.net/wiki/Release-1.2.2).
  Admin configured and working (see phpinfo()).
  (admin guide,
  admin guide,
  admin guide,
  admin guide)
3. Status: Done
4. Make sure your Apache configuration has KeepAlives enabled. KeepAlives are a trick where multiple HTTP requests can be funneled through a single TCP connection. Since the setup of each TCP connection incurs additional time, this can significantly reduce the time it takes to download all the files (HTML, JavaScript, images) for a website. Status: Done
5. Use a memory-based filesystem for Magento's var directory. Magento makes extensive use of file-based storage for caching and session storage. The slowest component in a server is the hard drive, so if you use a memory-based filesystem such as tmpfs, you can save all those extra disk IO cycles by storing these temporary files in memory instead of storing them on your slow hard drive. (http://www.magentocommerce.com/boards/viewthread/9037/) Status: Done (after slice upgrade to 512M)
6. Modify the configuration for your MySQL server to take better advantage of your server's RAM. Most Linux distributions provide a conservative MySQL package out of the box to ensure it will run on a wide array of hardware configurations. If you have ample RAM (eg, 1gb or more), then you may want to try tweaking the configuration. An example my.cnf is below, though you will want to consult the MySQL documentation for a complete list of configuration directives and recommended settings. Status: Done (after slice upgrade to 512M)