To convert your page to XHTML in FrontPage 2003, go to code view, right click anywhere in the code of the page and select the option to 'Apply XML formatting rules'.
This will not put the relevant DTD header into your page but it will convert your HTML into XHTML.
To move one step further to valid code you need to include a relevant DTD. You can find the right code more or less anywhere, but the excellent W3Schools site has a full set of tutorials on XHTML and is as good a place to begin as any: click here
Your CSS issue can be solved in any number of ways but to be honest about the quickest and easiest would be to reduce the size of the font and the length of the text in the hyperlinks. Neither one has to be reduced by much, but a marginally smaller font and shorter text hyperlinks will avoid having to use diffferent positional commands in the CSS which can knock things all over the place.
Try shortening some of your links from 'The Pentland Hills' to 'Pentland Hills', 'Scotland Gallery' and 'England Gallery' could both be simply 'Scotland' and 'England' since they both fall under the subheading of gallery. Yout top navigation bar gets overlapped purely because of the huge link at the end: 'Add UK Photos web to your favourites'. Have you considered 'Bookmark this site' or 'Add to favourites' instead ?
I dropped the font size to 76% in your CSS #nav line and in the #links A line and all was well.
Play around with it a bit and see how you get along.
I'd try the font size and hyperlink wording before you start hacking your page element positioning though.