I wish there was a way to add to Link's VELOCITY without adding to his actual X-Y coordinates. That would let us use the game's natural collision-detection and solve all of these problems.

And you know what? There's no reason why there shouldn't be a functions that do this. I'll see if I can't program up some functions:

void set_player_velocity(int direction, int speed);
Gives the player "velocity." Sets a direction and a speed. Since the player can only move 1 pixel, minimum, not portions of a pixel, speeds below 1 will be simulated by loading a delay value into a variable. The effect will be that the player will move 1 pixel per number of tics equal to the delay value. Passing 0,0 clears all variables.

void move_player_velocity();
Moves the player in the given direction at a given speed, provided that it doesn't cause walkability issues. Call it once before Waitframe(); in your while loop. Will do nothing if set_player_velocity is not set, or is set to 0.