Looks like the site is based around Drupal CMS, so it's probably just a plugin. I haven't spent long looking into it, but the random image is probably php code code executed on the server before the page is loaded.
If it's as simple as it sounds, about £350-£400 would cover it.
You could work with the designer to include your graphic design, but integrating it yourself without any web development knowledge would be a bit tricky. One way to do this would be to produce screenshots of the various pages...
Yes, I think Joomla's main drawback is that you cannot get it to automatically create menu items when you create a page. There are work arounds but it's fairly clunky.
If launching a one man crusade against Microsoft doesn't take your fancy, you could try adding the following lines to the top of your code ;)
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html...
As far as I can see it will keep on working but at greatly reduced effectiveness. Download the free trial of SEO spyglass and run some backlink checks on major sites - the vast majority are Yahoo links.
Yahoo site explorer is in the process of closing down. Correct me if In wrong, but my understanding is that SEO powersuite relies heavily on the Yahoo site explorer API?
A couple of things will determine how difficult this is:
Are you keeping the same server?
Do you have high search rankings at the moment that you want to maintain?
The logo is a very poor quality image. Try saving it as png instead of jpg.
Generally the site has too much content without any particular thing standing out. It's best to concentrate the user's gaze on what you want them to be looking at.