Writing about a bunch of sessile creatures got me thinking about movement and how different dimensions of movement are the kind of paradigm shift that you don't even notice it sometimes.
We're broadly accustomed to things that move in two dimensions, roughly. (Yes, we go up and down stairs, ropes, mountains whatever. If you consider the surface of the Earth as a curve defined by a pseudo-function, it has two parameters, not three. Thus two dimensions. And you people out there who want to point out that more than one person can be in a multi-story building at a time can hush.)
When they don't move in two dimensions, it changes things. It changes our approach to them. It changes their approach to us. All in ways much more fundamental than some special ability, like a gaze attack or turning invisible.
So here goes.
This one is actually fairly common, both for monsters and for PCs. For monsters, you have things like ropers, shriekers, otyughs. They either rely on sneak attacks and range, or the inclusion of other elements that mitigate their disadvantage. (Like a shrieker calls for other monsters who can move in two dimensions.)
For the players, this just means being caught in a net or something, and generally sought out. It's a challenge to be overcome rather than a mechanic to be used.
One possible way to use zero-dimensional movement in a fun way might be something like a teleportation fight. You have a room (or whatever) and want to either get away from or get at something else in the room. In order to do this, you have to figure out the right series of jumps, which are all limited to small areas - say, big enough to stand two or three people in, but not big enough to count as small rooms themselves.
This can either be a puzzle (figure out the right sequence of jumps to get to the door) or a chase (trying to catch a guy who keeps fleeing after a few seconds of contact, or figure out a way to cut him off from other jumps). Or even both. Maybe I'll throw together a room, because this is an idea worth playing with.
In the case of mis-matches where one side has 2-dimensional movement (the most common mismatch), the 2-dimensional side determines the engagement. After all, if something can't come after you, you can always stand back and hit it with lightning bolts until it dies.
Things that move only in a straight line. These are, methinks, the least innately common. They're just hard to do - moving in a straight line is still pretty restrictive. The only monster I can think of off the top of my head that does this is the Juggernaut from the Caverns of Thracia, and it cheats by being able to turn in place.
There is one commonly-used poor-man's model of this, though: sticking the PCs/monsters/creatures/whatever on a bridge, or isthmus. To a rough approximation you can only go forward and backward, not around. You could probably mix it up a little by making the line curved - in two or even three dimensions. Walking up a deformed helix in the astral plane to get to the Altar of Osmeden while everyone has a different native rotation around the helix and must all reach there at the same time while being stalked by the feared Astral Shark sounds like it might be a good time.
Generally, restricting the PCs' movement to one dimension forces them to encounter something if they want to go forward.
In the case of a mismatch, those with 2-dimensional movement still control the engagement, but the methods are different. Instead of just walking away, you trap the creature, go around a corner, remove its ability to turn, and you have to make sure you're going the right direction - else it might follow you. (So, on a featureless plane, only moving in one dimension isn't a drawback if all you want to do is get away.)
As mentioned previously, this is the default assumption of movement. Randomly pick a monster out of your monster manual; chances are it moves in two dimensions.
This is already pretty interesting without being changed up. Two dimensions gives you freedom for tactical engagements, under the assumption that the enemy's awareness is not as well-distributed as your movement possibilities. But (as with others) one thing that I don't see done very often (though sometimes) is to have the plane of movement not be flat. This includes tricks like walking on walls, around 'roller coaster' curves, shifting gravity, and so forth.
This type of movement is also the first one to be altered more by a definition of where you can't move than where you can. Walls, pits, lakes, etc. become obstacles that are essential to figuring out where you can and can't move, because the default assumption is that you can, rather than that you can't. Mazes, chasms, even the structure of dungeons themselves usually assume this kind of movement is prevalent and are designed for freedom or restriction in two dimensions.
One other way of looking at movement becomes potentially fun at this level: changing the way you move. Ice slicks are a fairly common example, which change the idea from, "I go where I want to be," to, "I gain the velocity I want to have (in order to end up where I want to be)." You could try the same thing with acceleration, though I don't know what that would look like or how it would play. There are also numerous other tricks, like switching directions (you go right when you mean to go forward) to translational or rotational instability (having to avoid falling down if you want to go forward; having to correct for a tendency to move away from your direction of motion, etc.)
A simple example: A room that has 'pits', changes the direction of gravity as you move across it, and has a strong wind blowing from one wall. Pretty difficult to navigate, that.
There are two main methods of movement in three dimensions: flight, and swimming. For the former, the PCs usually don't have it, and the NPCs do. For the latter, both the PCs and the NPCs usually have it.
I think movement in three dimensions is a large portion of why underwater adventures feel so weird. Yes, there's the fish/ocean/nonterrestrial theme, but take that and put it on the ground, and it loses some of its strangeness. There's just something alien about having that third degree of unrestricted movement. Another way to see this is if you say to the PCs, "Okay, you're underwater and can breathe just fine for whatever reason, but you have to walk along the bottom." It loses a lot of its charm.
Generally this is hard to run, at least with a mat, because your mat is in 2 dimensions and your characters are moving in three. No, I don't have any suggestions to help with that, sorry. What I usually see done is a kind of assumption of an X-Y plane and a deviation off of that (that happens with some rarity, depending on how enthusiastic people are about it). This is a shame. If you're going to design an underwater dungeon, town, or encounter, be sure to make it clear most things are not on the same level - why would they be?
If both parties are three-dimension capable, this also changes tactics considerably. You can swoop in from above or below. You can break off in any direction. Cornering someone is a lot harder. This is also an area where ranged weapons shine even brighter than they do in two dimensions, since they naturally operate in three. Be aware: if the party's flying, the wizard is going to outclass the fighter very easily for usefulness unless the fighter brought a bow.
Flight is where we see the effects of a mismatch between the PCs and their enemies most often, though sometimes it can go the other way. If you can move in 3 dimensions and your enemy is stuck in 2, you define the engagement again. Generally this looks like momentary contact, or projectiles. (A classic example is the roc dropping rocks on the party from high enough that they can't shoot it.) If you're on the underside of this, your first order of business is to remove your enemy's extra dimension of movement. Cut off his wings, trap him with a low ceiling, suck the air out of the room so he can't use it, whatever. Even if you have superior force, he gets to decide where and how you apply it.
Many ways to change this up exist. One of the simplest is clustering and restriction of means - for example, rather than natively flying themselves, the monsters are riding flying beasts, or a magic carpet or some such. Removing their mode of transportation also runs the risk of giving them a nasty fall (assuming a force like gravity), and it can be separately targeted. Also of note is that 2-dimensional traps can still work - while pits don't mean anything, nets do.
Effects I don't see very often but that might be fun to play with include changing the parameters of the movement itself, like above. Maybe three-dimensional movers move like airplanes, instead of like people with a tallness control. Or maybe there are pockets - like pits, canyons, rivers, etc. - that they can't cross and must go around. Maybe you can move in three dimensions, but those dimensions have certain rigid ratios - like you can only move on planes of a certain slope, or within certain solids.
As an example other than the ordinary flight/swim alternatives, I give you: Orbital Mechanics, the Mad Wizard's play room! In the exact center of the room is a huge black ball, humming quietly. This ball floats in the middle of the air, and gravity points toward it at all times. If you manage to avoid falling in after opening the door and crossing the threshold (because you kept a hand on the door or whatever), you'll notice harnesses hanging on the walls. These harnesses, when worn, shoot arcane missiles out of the chest, which allow you to scoot around. Better get to orbital velocity quickly before you touch the black ball, or who knows what might happen!
(In order to use this, you have to know something about orbits, so here goes. Prograde thrust (tangential, in the direction of travel) widen your orbit; retrograde will narrow it. (At apoapsis, the highest point, this raises or lowers your periapsis, or lowest point). The higher you are the slower you're moving; the lower you are, the faster. Radial thrust (toward or away from the black ball) will both lower the part where you are now and raise the part across the orbit, but not by much. Normal (at right angles to both) will change your inclination, or the angle of your orbit.
You can probably ignore or gloss most of that with modifiers; being in orbit when you're not accustomed to it is weird. And of course, there are strange scintillating bullet-shaped animals here that squirt a dark cloud out the back end and come at you, all mouths. They seem to know what they're doing...good thing you have time to react, so you'll miss them at the next rendezvous. Oh, and did I mention that you're trying to get to the door over there in that weird corner that looks like it has a bit of ladder you could grab onto?
Four or more Dimensions
(More than four and just four look pretty much the same at the table.) I'm not talking about movement through time or anything like that. The problem with four-dimensional movement is that, while we have the tools to mathematically analyze it, we don't have the intuition to grasp it, seeing as we're naturally creatures in three dimensions.
Unrestricted four-dimensional movement is probably boring. As far as the PCs can tell, it's no different from occasional teleportation, since in order to interact with the PCs the creature needs to be at a certain point on the fourth axis - and that doesn't move (at least relative to the PCs). If the PCs are given unrestricted four-dimensional movement...well, you're a braver (and probably brainier) GM than I am.
This can become interesting, however, with proper restrictions. Instead of being completely free, say the creature has to move in a certain relation of the fourth dimension to the rest - like a tesseract. Then, with observation and a little smarts, the PCs can start to predict points of contact with their three-dimensional existence, and plan accordingly. The same is true if you give them access to four dimensions - the fun will come from observing those restrictions and seeing what freedom you're allowed within them. For example, maybe you can step through this wall but not that one because of the local geometry. Or maybe you can figure out a way to steal the Fire Emerald off its Pedestal without setting off the Rolling Rock of Doom.
Side note: ethereal and astral travel could be used as a sort of poor-man's fourth dimension, but I feel like that's reducing something really potentially cool (you have a whole other world in those planes!) to something rather quotidian.
A simple, restricted example of a challenge related to movement in the fourth dimension is the dungeon room that's a tesseract. In order to construct one, make each surface (floor, ceiling, walls) a potential floor. Give them all kinds of accoutrements, too - essentially you're stuffing six rooms into one, and allowing them a way to interact.
Then, label them 1 - 6, or A - F, or whatever. Then, for each side of one floor, (NESW) choose a number/letter it connects to, while making sure that it's not the one it should connect to in 3 dimensions.
In a way, it's like a teleportation maze where you can see everything in the maze at the same time, with the added complication of looking a little crazy to the eye, because you never change orientation but the room does.
Anyway, I hope that helps someone come up with something cool. I feel like I hadn't really been considering movement paradigms enough in my designs, so I reckon I'm probably not the only one.