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.
Moving one square vertically will trigger an opportunity attack.
The relevant general rule is simply:
You can make an opportunity attack when a hostile creature that you can see moves out of your reach.
(PHB, p. 195, "Opportunity Attacks").
And the rule for figuring ranges on a grid, which includes reach, is:
To determine the range on a grid between two things ... start counting squares from a square adjacent to one of them and stop counting in the square of the other one.
(PHB, p. 192, "Variant: Playing on a Grid")
D&D is an exceptions-based system, meaning that general rules apply unless there are more specific rules in place, and there's nothing in the single paragraph of rules for flying in combat (PHB p. 191) that change how these rules would operate.
So, if C1 can make melee attacks against C2, they are within one square of each other -- that is, they are adjacent on the grid. If C1 moves so they are more than one square away from C2, C2 can make an opportunity attack (and vice-versa). On a grid, all movement is in increments of one square, so any move from either combatant that puts more than one square of distance (making them no longer adjacent) between them is sufficient.
How big is a vertical square? The rules just say that a square "represents 5 feet". There are no specific rules for how to use a grid for three-dimensional combat (and remember that the rules for a 2D grid are themselves both optional and lightweight). The most direct interpretation of the rules is that a square on the grid represents a 5' cube of space. Thus while an active, flying, Medium creature will, strictly speaking, have bits of them sticking outside of the boundaries of "their" cube, what really matters is that any creatures who occupy any of the 26 adjacent cubes are within their one-square (or one-cube) reach.
Best Answer
(The bulk of this answer concerns paper miniatures that stand up on the battlemap. For information regarding tokens that lie flat on the battlemap, see Addendum 2 below.)
It's difficult (and not really necessary) for paper miniatures to be the same scale as the map. You can approach this in many different ways, but the solution you choose has to be based on what looks good to you, because there isn't really a correct way to make paper minis.
Here are a couple of my own illustrations as examples: A lizardfolk greaser and his slavering wolf companion.
They're basically to scale with each other, right? Sure they are.
The typical scale for tabletop battlemaps is one table inch to five D&D feet. Assuming that's what you're doing, I'll be treating a square in my image editor as "one square inch" in paper terms. From your question, I get the impression that the minis you made look sort of like this:
The humanoid figure takes up most of the width of the square, and looks great, but the wolf has to be squeezed to fit in, and it does not look great.
Of course, if the lizardfolk is about one inch wide and over two inches tall, and we take the figure to be to scale with the surrounding map, that means he's over ten feet tall, which is not what I had in mind. To make these tokens be (more or less) in proportion with the five-foot grid, we can do something like this:
The lizardfolk is just over an inch tall, which means he's "really" about 5'9", which is what I was going for. The wolf appears to be five feet long and two and a half feet tall. When these guys are placed on a battlemap, your table will look like a real dungeon with a real lizardfolk and a real wolf that all got shrunk down to 1/60 scale. That may be exactly what you want!
...But for my money, they're both too small. (The squares in these images are probably not one-inch squares on your display, so look at a ruler to see what I mean.) I prefer for my handmade minis to be bigger, so they're more visible and easier to pick up (and so my players can better admire my unparalleled artistic talent). When I printed out this lizardfolk recently, I made him a little over two inches tall, as seen in image #2 above—it didn't bother me or any of my players that he was grossly out of scale with the surrounding battlemap. That kind of abstraction is totally allowed.
The "wideness" of the wolf is still a problem, though. If you print it out at the scale I picked for the lizardfolk, it's definitely too big. It takes up two squares on the map, which a Medium-sized wolf is not supposed to do:
If we're sticking to one-inch squares, then it's going to be tough to determine what space this wolf is occupying.
Here's a compromise that I rather like:
The wolf is spilling out of its square a little bit, but that's manageable. The lizardfolk is "technically" about seven feet tall, but I don't mind. What's important to me is:
Addendum 1: Printing Out Standing Miniatures
(This may go beyond the scope of the question, but I hope it makes my answer more clear.) Regardless of the scale you choose, you can print out your minis in a few different ways. Here's how I do it. In my image editor, I put two copies of the image together, one flipped 180 degrees so they meet at the head (with a bit of space in between).
I make sure the grid really is one inch squares, and then I print this out on cardstock. The dotted line indicates how I cut the guy out, leaving about 3/4" at each lizardfolk's feet.
Then I fold between the heads, I fold below their feet, and I glue the two bottoms together, like this:
You could also fold the "bottoms" out and glue the backs of the two images together, creating a ⊥ shape. If I did that, I'd probably glue a square of cardboard to the bottom to make it sturdier.
Addendum 2: Tokens that Lie Flat
I don't think any of the above solutions work if your character-representatives are going to lie flat on the battlemap. Any character who's big enough to see is going to be too big for its square—and everyone looks like they're lying on the dungeon floor. This is probably a matter of personal preference, but I don't like the idea at all!
What I'd do instead is use only the characters' portraits for tokens, maybe with some borders. Maybe something like this:
I could print these out, glue them to some cardboard, and cut them out really fast. They'd be easy enough to see and manipulate, and I wouldn't have to worry about scale at all. They'd travel well, too: I could toss them in a dice bag and not worry about their being bent or torn. (Also, I'd only have to draw the characters' heads, which would have saved me a few minutes.)