changing the 404 message

I made a huge mistake. Last week I changed the structure of my website. I had a directory that looked like mysite.com/episodes/voyager/file.html
Well I went from just doing star trek reviews to doing movie reviews as well, so I changed directories around and now all those links on google are dead. the links would now be mysite.com/main_docs/trek/episodes/voyager/file.html

Well this really bothers me because I had no idea how over the past 4 months my site really began to catch on to search terms. Like, if you type in "Voyager Prime Factors Review" my site is number 6 on google. But again, the link is now dead.

So I'm not sure the best way to handle this. Should I change my 404 document to say "this page has moved, click here" so that people can get to the proper page. Should I do some sort of automatic redirect? should I put a message asking people to click to the home page?

I'm just not sure what to do, or how to change a 404 message. I had always thought 404 page not found message was client side; not server side, yet I have in my main directory of my site, a file called something like https_404.html

Umm, never mind, I had a buddy tell me that creating a redirect could be a red flag for search engines, and I am better off not doing that.
It would also seem that those pages I thought were called https_404 is actually things called 504.shtml
Don't know what it does, but i am leaving it alone.

My solution was to just to create the old directory, simply put a quick message that this page has moved, and gave a link to the homepage. I only had about 10 documents to do that with anyhow, so it was not big deal.

Oops, I meant to add that second post as an "edit" to my first.
I'm so tired I'm not thinking straight. Could some mod just please delete this entire thread. Thanks.

You could use a 301 redirect, which Google will honor without penalty and web browsers will honor invisibly. How you do it depends on what web server you specifically have, but it's usually easy.

I agree with andrew, a 301 redirect would have suited this perfectly.