Hi Bastian
This process can look quite daunting at first, but can be quite easy and fun to do once you know how.
First, I always look at two criteria for redirecting a page - incoming traffic and incoming links. If a page has a decent amount of either, I will redirect it. If it doesn't, I let it 404.
Finding URLs with incoming traffic can be an easy one with Analytics. If you have Google Analytics, login to the dashboard and click on Traffic Sources -> Sources -> All traffic on the left-hand side. Once it's loaded, just below the graph you will see "Primary dimension" - at the end of this line click "other", then from the dropdown menu, click traffic sources -> landing page.
You'll now have a list of URLs that people have used to enter your site. Pick a time frame of about 3-6 months and see how many people have entered the site via that URL. If you have URLs with 5 or more visits (or whatever threshold you think is best), save the URL as one that will be redirected.
I think it is important to redirect landing page URLs as it is the very start of a user journey that people have used in the past. It can be off putting to see a 404 straight on entry, so ensuring that the user is taken to an appropriate page via a redirect is highly recommended.
Redirecting URLs that have been linked to the in the past can be an important step to take to ensure that you keep all of your link "strength" or "equity" when you relaunch. For this, we can use SEOMoz's Open Site Explorer.
Go into OSE and type in your site's URL. Once loaded, click the "top pages" tab. Export the results into a CSV and open that with Excel. Enable filters, which can be done by clicking "data" and then "filter" while having any of the top row cells selected, and then filter out results in the "inbound links" column to exclude results containing less than 2, 3, or 5 links, depending on your threshold.
You'll then be left with only the pages on your site that have links pointing towards them. Now, rather than just redirecting all those pages, it is worth checking each URL in open site explorer again to look at what links are going to those pages. This may take a bit of time, but this way you can ensure that you will only pass on links that you're happy with. You may have a page that has 5 inbound links, but on review you think those links are spammy. Don't redirect this page and you will not have the new site associated with these links.
Hopefully at the end of this you will have a good list of URLs you should redirect. Try and redirect them to the appropriate pages on your site for a good user experience The rest you can leave to 404. If some pages don't fit in the new structure but you want to keep for user or link reasons, redirecting them to the root domain is no problem. And to add, I've redirected thousands of URLs to a root domain before and have not had any adverse effects.
Remember to update your XML sitemaps and resubmit them to Google/Bing webmaster tools as well once you're done.
Hope this helps and all the best with your relaunch!