See, currently the Endermen are the most interactive mob extant in the Minecraft world. Not only are they able to pick up and place blocks just like the player, but they're neutral towards them until they notice you looking at them. They then display teleportation abilities, unseen in any other mob, and to cap things off they're very divergent in proportion relative to the other mobs too, being three blocks tall instead of two with long spindly limbs and a distinct mouth that actually moves when they're angry.
I have an idea, therefore, as to how they can be given even more importance in the world, especially in relating it to the Nether and recent developments in it.
Now, we know that Jeb has recently added generated structures that seem to resemble raised roads or aqueducts to the Nether, indicating habitation by some creature, probably not the Zombie Pigmen though they do display communal association in their vengeance-wreaking reactions to player attacks. Suffice it to say, this is indicative of there being some organism that lives in the Nether.
The Endermen have strange proportions, strange abilities, and they can move blocks around. They're different to every other mob on the surface world by vast stretches, and they're even harmed by water, even if it's just rain. My suggestion then is that they don't come from the surface world, they originate from the Nether.
More specifically, I propose that Endermen have a goal of creating Nether portals on the surface. They take blocks from a localised area (specially marked in the code, similar to slime spawning) and try to build the 4x1x6 frame of a portal.
The Ender-portals and their grim purpose
And I have ideas beyond that as well. When they complete these portals, no matter what materials they are initially made of, the blocks become Obsidian (or some special material to distinguish it as an Ender-portal, possibly weaker than Obsidian for ease of destruction), and the Endermen then stand in the portal like willing sacrifices and wait for sunlight to ignite them, thereby lighting the portal.
From there, the Endermen's masters, the Enderlords (or somesuch name), can step through to the surface world from the Nether.
Immune to fire like every Nether mob to date, they would have no fear of the sun, demons walking our earth. In code, this would mean that the portal would have a special marking (like that special block or a damage value like wool) to allow the master mob to spawn in its vicinity, sort of like a big mob spawner.
And if the Enderlords can build structures in the Nether, they can build structures on the surface world, guarding their portals with strongholds and castles, building throne rooms and dungeons with strange-yet-familiar blocks. These would be much more complex and intelligent mobs that could actually pose a threat to the player and give them reason to build defenses and seek out the Endermen. Perhaps they'd even spread a strange Nether contagion to the earth like grass beneath their feet, which made enemy mobs more dangerous or allowed Pigmen or more Endermen to spawn.
The Ender Pearl
The Endermen teleport because that's how they are sent to the surface world to begin their tasks, and they move blocks around to build a way through for their masters. Perhaps the Ender Pearl would render you invisible to Endermen or their masters, the Endermen themselves certainly only pay significant attention to you. Alternatively, the pearls might serve as compasses to the nearest Ender-portal, allowing you to either hunt a large group of Endermen back to their worksite or kill one to get their "map" of sorts. In effect the pearl would be like a little internal compass they use to navigate, which you cut out of them after killing them.
Impact on Gameplay
But what would this mean for gameplay? Well, when the Endermen spawn at night, their first goal is to co-operatively build a portal. So you would spot an Enderman and then carefully follow him to find where they are grouping together to build the portal.
If you left the Endermen alone, there's not necessarily a certainty that they'll actually manage to build one; sand/gravel could swallow the portal in a cave-in before they can get to it to ignite it, or water could flood through it as a block is removed and kill the Endermen getting too close, or sunlight could just never reach the portal site underground or in a cave, and sand/gravel would still fall if they put them on the top row of the portal, breaking the shape. Even if they did start causing trouble, in day 1 you can make a stone sword, potentially even an iron sword, and go hunting the Endermen with some reasonable success, especially once you develop a bow during the daylight hours.
But if you're worried about coming under attack soon (possibly in the early days of a world where your defenses aren't too great) you want to follow them to be sure. In theory, a bucket of water would be the best weapon against this portal-building aspect to the Endermen because water puts out Nether portals and Endermen die in water. Plonking a water source inside the portal then would destroy it, effectively, so there's no reason to call this overpowered, especially since the Endermen are slow-moving when they're not teleporting to attack you so the portal would take time to build. Additionally, between calamities that may befall the Endermen whilst building and the time it would take them and the limited chunks they could build in, you don't have to worry about your world getting pock-marked with portals summoning demon overlords.
Later on, you could build a portal from Obsidian yourself to have a safe route into the Nether, or if you wanted a challenge, you could deliberately find a quenched Enderman-portal and ignite it yourself. This gives structural defenses built by players actual purpose, as well as a top-tier adventuring challenge that is, to some degree, controllable by the player. Stopping a portal being built or ignited is a good goal for a low to mid-level player, whilst combatting the Enderlords head on is definitely high-level challenge.
Minecraft endgame: The Coming of the Enderlords
If you support this idea, check out the getsatisfaction thread and upvote the reddit link!