I am building an app for an Android tablet that will control an Arduino microcontroller board (paired via bluetooth). However, the tablet will also be paired via Bluetooth with my Android phone to share the phone's internet connection. Can I pair the devices this way simultaneously?
AFAIK, bluetooth connections can occur simultaneously as long as their operational bounds do not overlap. In other words, you cannot connect two bluetooth headsets at the same time, but you can connect a bluetooth keyboard and bluetooth mouse to the same device at the same time (I personally have tested this last scenario, and it works!)
So in your case, I assume the steps you would take would include making sure that the two communication streams don't require any of the same functionality, which sounds as if it would be possible, since one is strictly for internet availability. If you connect both and they won't pair with the device simultaneously, you probably won't be able to. But if they register as different types of devices (under different bluetooth "profiles", for example) you may be in luck!
Sorry there's nothing definitive. The bottom line here may be trial and error. If they don't work initially, you may be able to set up the Arduino to register under a different "profile" when it connects to the tablet, so as not to interfere with the internet connection coming from the phone.
Some devices have a concurrent connection limit due to power/resource constraints (usually cheap feature phones like my old SEMC W880i only allowed up to 5 connections at a time). Also some apps like bluetooth file transfer can be set up to limit max simultaneous connections. Generally, Android's bluetooth implementation does not force such a limit though. I've been able to use bluetooth keyboard, mouse, game controller and a headset the same time. Bluetooth internet sharing capability depends on your device though, not every handset/tablet maker implements this (most aftermarket roms support this however).