When I am prompted to restart after uninstalling software, is a shutdown okay too?
The process explained
When you install or uninstall a program, it will register or unregister the usage of one or more .dll files.
.dll files are placed in the Windows system32/syswow64 directory when installed, and they are common files for many applications. These files often are in use at the time of uninstalling a program, and as such Windows has a built-in system to check for unused (after uninstall, no other program is using these files anymore) .dlls at shutdown to remove them when the applications that were using them are terminated (basically the uninstaller tells Windows to verify the files for deletion).
When Windows has closed the programs, it will then delete any file that is no longer assigned to a program to clean up the computer.
Rebooting necessary?
You may be wondering, if that's all there is to it, is rebooting necessary? Yes and no. Basically, you have to make sure Windows will be shutdown properly or risk leaving unnecessary files behind. If you know your computer is stable, and you will be rebooting it in a matter of hours, you really do not need to reboot your PC right now. If you regularly put your computer to sleep/hibernate and don't want to reboot as much as possible, you better do reboot for an uninstall because sleep/hibernation may cause a system to shutdown unexpectedly in the long run, which can keep files on your PC that do not need to be there anymore.
Is it harmful if these files remain on my PC?
Technically speaking, no. It's a waste of diskspace, yes, and if it happens with too many files, it may slow down your PC, because every .dll that is loaded with Windows will be adding to resources used to operate your computer.
Is there a difference between using reboot vs shutdown?
Both options will close the programs and run the necessary cleanup routines, so both are fine to use. Windows just notifies you to reboot because that way it can guarantee that Windows is being kept tidy.
Is it okay if I hold the power button so the computer is turned off immediately?
No. This is not a normal shutdown, and thus Windows will not be able to run the cleanup routine. You can see this option as if Windows was crashed.
One thing to note is Windows 8/8.1 has a hybrid boot option that's enabled by default (or at least for me it was). This doesn't reload the some kernel files at boot to achieve a faster power up/down state. However, this feature is bypassed if you restart.
If you're messing with software that uninstalled drivers it may (also) be wasting resources. I always like a reboot better for this reason, although I doubt it would really help unless I uninstalled a driver/updated a service pack/etc., although Windows might intelligently know to not hibernate the kernel and do a cold boot.
EDIT: it seems as you can do a "standard" shutdown by doing this:
Shutdown /s /t 0
It will still use the hybrid boot the next time your computer turns on. You can turn off hybrid boot in control panel.
More about hybrid boot...
It seems as Windows is the most affected by restarting, but I think that it might be best to restart other OSes. For example, if uninstalling PHP, restarting the computer would restart Apache, and that could avoid some errors if Apache doesn't realize PHP was uninstalled. General rule of thumb: reboot while you grab a cup of coffee and come back. It'd be best just to do that to make sure everything runs smoothly.
A restart is a shutdown followed by another power up. It would not matter, since any application prompting for reboot is installed within the OS. There is nothing it can do on its own when the OS is not available (during restart and shutdown as well). So for the program,in most cases it would not even know if it is a reboot or shutdown. Maybe you should do some research if it is a BIOS upgrade or something low level you do, otherwise it should be safe.