The only thing that absolutely requires a reboot is modifying the kernel. Any process can be killed if the program (or some library or other file that it depends on) has been upgraded, but that isn't the case for the kernel.
Actually, it's possible to patch a Linux kernel directly in memory sometimes. There are several tools that work at least in some cases: Ksplice, Kpatch, kGraft… Each of them works in some simple cases but not all; they typically work with security updates, as those don't change any internal interface (especially data structure formats), but not to upgrade between kernel versions. Ubuntu LTS supports kernel patching using livepatch since 16.04 with the 4.4 kernel with a proprietary client.
Although anything that isn't in the kernel can be upgraded on a running system, it still requires restarting the affected processes. On a server this means restarting the servers that use an executable, library, plugin, data file, configuration or other dependency that has been updated. On a desktop machine, this can mean getting users to log out and back in (e.g. if it's a bug in the graphics driver). Determining exactly what needs to be restarted can be difficult as it depends on the exact nature of the bug fix and how the program is used. Rather than go through the huge amount of work needed to determine this precisely, Ubuntu plays it safe and recommends a reboot in packages that think that restarting the service would be too fiddly. The way it works is that you get a prompt to reboot when a package's post-installation (post-upgrade, in this case) script declares that a reboot is required (see How can I tell what package requires a reboot of my system?).