You sprite character gets snagged on the intersections between two tiles. See the following diagram, which depicts the situation at the start of your collision routine.
Mario was moved to the right due to player controls. This will place the sprite in the three tiles. Then, you perform the collision detection on downwards Y. Notice the point in the blue circle: this will detect a collision with the second block and tries to resolve it by setting the Y coordinate to the upper bound of that block, effectively suspending Mario in mid-air.
As soon as the player releases the key to move Mario to the right, the sprite will not move into the wall, and the point that previously would detect a collision, will not register a hit. This will allow Mario to fall to the ground.
The quick and dirty resolution to this problem is resolving X collisions first, and only apply gravity when the player is not on the ground. If you would keep the gravity, the same problem would occur when walking around (this is the 'trippy' behaviour you have seen already after swapping the X and Y check ;) ).