This is a pretty common problem with high-powered electric motors, such as the one in your fan. Inside the fan's motor, there are coils of wire which will create a magnetic field when you push a current through them, which is what turns the fan. Once the fan is spinning, this arrangement will also produce a voltage across the coil, which resists further current flow. However, for a moment when you first connect that coil, the magnetic field hasn't had a chance to build up yet, which means the coil of wire looks like a short circuit. That's not a problem for the fan itself, but for other devices on the same circuit, for a moment it will look like there's a short circuit right next to them. As a result, they will see greatly reduced voltage for a moment every time the fan starts.
The easiest solution is generally to move one device or the other to a separate circuit, so that they won't affect each other as much. Since you only have one circuit, you can't completely do that, but you still may have some luck with moving one device or the other to a different outlet across the room, or in a different room. They definitely shouldn't be on the same power strip in any case.
If that doesn't work, our next option is to make the devices play nicely together. As you've noticed, some devices are more tolerant of this short-term brown-out condition than others -- your computer continues to function fine, but your modem/router loses power and reboots. Most modern computer power supplies are designed to work anywhere in the world, and as such have a 'universal' input, capable of using anywhere from ~90V-250V. So when your fan starts up, if the voltage drops from a nominal 120V (or whatever it is in your country), there's still a lot of margin for the power supply to continue functioning. Your router's power supply is probably not like this, and expects a particular input voltage.
However, it's very likely your router's power supply can be replaced with a universal one which will function better under a brownout. (This is assuming your router/modem has an external AC/DC power supply, which most do. If yours takes in AC directly, this won't work.) Check the label of your router's (and modem's, if they're separate devices) power adapter. Your new adapter will need the exact same output voltage rating, and a current output rating equal or greater than the one you have now, with a wide range input voltage rating. Something like this might do the trick: 30W Universal Switching AC/DC power supply.