Most of the logic you ask for I wouldn't place in either tile or prototype. Send events to the map and let it be responsible to handle them. They are also your major tool in fighting depedencies. Some class enemy doesn't have to know what a tile is, just because it moves on them. It will not go and call oldTile->onLeave(me) and newTile->onEnter(me), but it will send event MoveEvent(me, fromPos, toPos).
This event will end up hitting the map which will grab the two prototypes and call their functions, passing the relevant tiles as parameters. If you are worried about too many dependencies, don't have everybody call functions on everybody else. Yes, this event system will be some form of "global", because it's the module everybody will use to communicate with everybody else.
So I take it that "MoveEvent" is something sent to the game's event queue, and that it is the current map is implicit? But does this also mean that a global is okay in this circumstance?