I think the reason why the player is going halfway into the rectangle before being pushed out is because of when you handle the collision detection. Let's try stepping through the code one at a time, lets say you start to the left of the rectangle and you press and hold the right key.
At the beginning of the code you gave us you do the collision handling. Because you're not intersecting with the rectangle right now, the collision handling section is skipped because there is no collision.
Next you have your keystates. The game detects that you are holding the right key so it moves your player to the right, then it draws the player in this position. Now this is important to note that the player is drawn right after he moved, meaning the collision detection has not happened yet.
Next you go back to the beginning of the loop and here you run the collision handling because, this time, your player is inside the rectangle. After the collision handling is finished the player is no longer in the rectangle.
But once you reach the input handling you move the player back inside the rectangle and then when you draw the player, he is drawn inside the rectangle because you won't handle collision until the next frame.
If you let go of the right key, then the collision handling will occur like always, but this time the player won't move because you are no longer handling any input. The player is drawn outside the rectangle because you haven't moved him.
So in short the player is drawn right after he moves, before the collision handling can occur so he is drawn inside the rectangle and his position isn't corrected until the next frame. But even if his position is corrected the next frame, if you are still holding down the right key he moves into the rectangle again so in the end you're still in the rectangle.
if you restructure your code so the collision handling occurs after the player actually moves then your problem with the player going inside the rectangle should be fixed.
As for the problem with things moving too fast you'll have to find a way to deal with it yourself. For the most part you can just limit the speed of everything so they can't go through objects, but if thats not possible there are other methods. Since you're using axis-aligned rectangles (non rotated rectangles) you could check out http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084 to learn about swept AABB collision detection. This is basically where you predict where the player traveled during the frame and check if the course he traveled through intersects with any objects and handle collision accordingly. I think that limiting the speed of the objects are good enough if you're just starting out with game development, but if you want you can always implement more advance techniques if your game needs it.