Let's say I'm working on a 3D first-person shooter and the boss is a stickler for realism, and orders me to implement the bullets as tiny projectiles that travel, say, 1000 meters per second. What might be some implementation difficulties, gameplay experience changes, etc. that would result from that decision?
The main problem is tunneling.
Game physics engines typically use discrete collisions. That means they advance all the bodies by one short time step, then check if they're intersecting, and handle collisions in response.
This works well for medium-sized objects at medium speeds.
But if you have a small object (like a bullet) moving very fast (like a bullet) then a single time step might take it from just about to hit some poor person's face to just past the far side of that person's head. Since the objects are small, they don't intersect in either position, and the physics engine says "great, no collisions to deal with!" and moves on.
But from a player's perspective, a bullet just went through someone's head without affecting it, like it had "quantum tunneled" through it.
Ways to fix this are:
Bigger, slower collision objects (you can probably get away with extruding the bullet's collider along its flight direction so it's more like a flying lance and more likely to intersect rather than tunnel completely through. You just need to make sure your gun doesn't hit you or things behind you when you fire it, or hit things on the far side of a wall if you shoot directly into it)
Smaller time steps, but this means more calculations which is slower.
Continuous collision detection, which models motion swept over time rather than as a series of discrete hops. This can be even slower still - especially against complex collider objects.
You may also find some physics engines rebel when you try to make objects travel above a certain speed. They might refuse, by enforcing an arbitrary speed limit on everything (usually a good thing, as it clamps how badly things can explode when physics glitches happen, and bounds the worst case for some calculations, helping us get faster & more predictable performance). Or they might behave unrealistically - a tiny 8-gram bullet sending a 200 kg soldier flying because the collision system doesn't handle momentum transfer correctly for such huge disparities in mass & velocity. You might need to treat the bullet as a trigger volume if the impact reactions get unruly.
For most games it doesn't make a difference.
Take the Counter Strike series, for example. It simulates firearms combat on rather short distances. On the distances where the average CS shootout takes place, the gameplay difference between the simple hit-scan solution and the far more CPU-intense physics simulation of bullets would be negligible.
On the other hand, there are also games which simulate firearms combat over far larger areas. When you fight over distances of hundreds of meters, bullet drop and bullet velocities start to make a difference. Such games can benefit from a more accurate simulation. But keep in mind that it makes the game harder to play. Players need to develop a feeling for how far they need to lead their target and how far they have to aim above with what gun on what distance. That means a much steeper learning curve and a much wider skill gap between newbies and experienced player.