One of our boxes is running Ubuntu 8.04 LTS. Most Ubuntu package upgrades are trivial and don't affect availability much. How do I tell which packages are going to cause an outage before applying them?
Any package which installs/upgrades a running daemon will need a restart for that daemon. This is usually a very quick process, just a blip in service availability.
The only packages which need a reboot are kernel updates. You cannot upgrade a kernel without a reboot.
glibc updates may need you to restart a lot of services, or a reboot. However, given that most Unix services are still short lived due to the forking model, glibc updates are handled automatically.
The best way to know what is going to cause an outage is to actually apply them to a test machine and see what breaks. Testing is always a good idea.
Even the kernel upgrades that need a system restart will not cause you an outage - The old kernel will still be loaded and running until you restart the system in the future.