lucy24 - 4:03 pm on Aug 5, 2013 (gmt 0)
If an old URL corresponds one-for-one with a new URL, then yes put in a redirect. Otherwise leave it at 404 but make sure your humans get a nice 404 page that gives appropriate information and matches the overall look of the site.
The subject line made it sound as if the alternative was a global redirect to the root. This is not a good idea, so I'm glad you are not contemplating it :)
Updating external links is always good, though it may not always be possible. If the linking sites are actively maintained, then someone at their end checks periodically to ensure that outgoing links remain valid. Uh... don't they? Worst case: linking sites discover the 404, don't have the resources to investigate individually, so they simply remove the link. If they are desirable links you obviously want to avoid that.
Do make sure that all site-internal links are correct.