[RPG] How many squares can a creature larger than Medium with a speed of 30 feet move on a 5-foot square grid map

A creature that, because of the creature's size, provokes attacks of opportunity for entering a foe's square provokes attacks of opportunity when entering that foe's square even if the creature enters that square by taking a 5-ft. step...

The rules cited in the question are from two different places about two different things. The 5-ft. step rules don't care about the creature size rules, and the creature size rules don't care about the 5-ft. step rules. The two rules are managed independently and don't interact. Thus, when a Tiny, Diminutive, or Fine creature enters an opponent's square, it provokes an attack of opportunity even if it entered that opponent's square by taking a 5-ft. step. That's a function of the creature's size exclusive of the creature's 5-ft. step.

Example 1
A Tiny, Diminutive, or Fine creature takes a 5-ft. step when adjacent to opponent and within that opponent's threatened area that doesn't provoke an attack of opportunity (because of the 5 ft. step) and moves into his opponent's square which does provoke attacks of opportunity (because of the creature's size).

When a Tiny, Diminutive, or Fine creature takes a move action to move within its opponent's threatened area then enter its opponent's space, the creature probably should provoke attacks of opportunity twice, once for the movement within the creature's threatened area and once for entering the creature's square, except that the FAQ (see below) says to treat the opportunity granted by moving within a creature's threatened area as part of the same movement needed to enter a creature's space. Thus a typical Medium creature gains only one attack of opportunity against a Tiny foe that takes a move action to enter the creature's square.

Example 2
A Tiny, Diminutive, or Fine creature takes a move action to travel 30 ft. to enter an opponent's square. The creature provokes an attack of opportunity when moving within the opponent's threatened area as normal then can enter the opponent's square with impunity.

It's sort unfortunate that two attacks of opportunity aren't provoked. It might've saved the Dexterity 13 commoner with the feat Combat Reflexes from death by house cat.

...And the FAQ agrees

The Pathfinder Roleplaying Game Core Rulebook FAQ contains the following exchange:

Question: In the section on Tiny and smaller creatures, it says that entering a creature’s space provokes an attack of opportunity, but typically 5-foot steps don’t provoke an attack of opportunity. If a Tiny or smaller creature took a 5-foot step into a creature’s space, would it provoke an attack of opportunity?
Answer: Yes. Even with a 5-foot step, a Tiny or smaller creature entering a creature’s space provokes an attack of opportunity (unless it is using a more specific ability to avoid the attack of opportunity such as the Monkey Shine feat). This doesn’t mean that a Tiny or smaller creature entering a creature’s space and moving out of a threatened square with a move action provokes two attacks of opportunity from that creature, for the same reason that moving out of multiple of a creature’s threatened squares in the same move action doesn’t provoke two attacks of opportunity.

This exchange was added to the FAQ in Jan. 2016.

From the Player's Basic Rules, page 71 (or PHB p. 191):

In contrast, you can move through a hostile creature's space only if the creature is two sizes larger or two sizes smaller than you.

An ogre is a large creature and elves are medium. So an ogre can't move through an elf's space. In your previous example, if we have a 10-foot wide passageway with two elves standing side by side, the ogre can't get through without killing one of the elves or forcing them to move.

The rules on squeezing into a smaller space are for an ogre trying to move along a 5 foot corridor. The rules on creature size that you've quoted back this up—the ogre isn't actually 10 feet wide, that's just the space he controls. So he can move through a 5 foot wide gap, but it's cramped and he can't move freely.

Now, you might be thinking that it's a bit unfair on the ogre if the 2 elves can form an impenetrable barrier against it. As you've said, he'd rather shove them aside than squeeze between them. And he can do just that! From the Player's Basic Rules, page 74:

Using the Attack action, you can make a special melee attack to shove a creature, either to knock it prone or push it away from you. If you're able to make multiple attacks with the Attack action, this attack replaces one of them.

The target of your shove must be no more than one size larger than you, and it must be within your reach. You must make a Strength(Athletics) check contested by the target's Strength(Athletics) or Dexterity(Acrobatics) check (the target chooses the ability to use). If you win the contest, you either knock the target prone or push it 5 feet away from you.

So you're right, shoving is the ogre's answer here.

Now, with your new example, (2 elves in a 15 foot corridor with a 5 foot gape between them), things are different. The ogre does indeed have to squeeze between them. Fortunately for him, it's not going to matter all that much.

Why? Because he's almost guaranteed to be moving on his own turn. Unless there are more enemies than just the elves, he's not going to provoke any opportunity attacks while squeezing, and he can attack before or after he squeezes. So the only squeezing penalty that is actually going to apply to him in this situation is the double cost for movement.

Note that if he stopped between the elves, all these penalties would apply to him. That makes sense though—standing between two enemies with not enough space to move around in would make it difficult to dodge attacks or attack effectively.