How can I easily verify if a core or module update has not broken anything?
In general Drupal core updates should not break Drupal core. If you upgrade stable community modules to a newer stable release -- again you should not encounter regression error problems.

That being said and long as your not the edge with alot of modules it shouldnt be such a huge worry -- but I similar worries. Backup, Backup, Backup always.

I doubt you have 1000s of unique pages. There are tools like Selinium, or JMeter or Java's The Grinder that let you script interactions with a webpage for known results. You could script your set of possible necessary functionalities on a handful of generic pages.

There's no way around testing if you really have to test and assure error-free site usage.