Even if I have a VPN configured to auto-connect in Linux, there is a brief moment where it is connected to the Internet, but not utilizing the VPN. Doesn't this provide a vulnerability? How can I protect myself?
Depending on your vpn software that's normal behaviour.
Configure a firewall that only allows connections to your vpn provider over the public network and force everything else to go over the vpn.
iptables -P OUTPUT REJECT iptables -A OUTPUT -d <VPN_SERVER> -j ACCEPT iptables -A OUTPUT -s <VPN_ADDRESS> -d <VPN_NET> -j ACCEPT
VPN_SERVER is your VPN provider's public address,
VPN_ADDRESS is your address on the tunnel interface and
VPN_NET is the VPN network in CIDR notation.
You can also do this with routes instead. When you setup your internet interface, instead of loading a default gateway you load a static route to your vpn server. No host other than your local neighbors and your vpn server will be reachable until you get a default route from the vpn provider (through the vpn).
Both approaches get the job done, but the firewall approach includes an insurance policy for free.