Q:

Doesn't the slowing of time when travelling at almost light speed create a paradox with an observer?

Disclaimer: I am extremely new to this and have no proper knowledge of this subject at all, this is just an idea that I had which I want to properly understand. I don't have any knowledge of necessary equations, proper terminology, etc.
In Sci-Fi movies that involve travelling at  almost the speed of light, there is sometimes a plot where it involves a character travelling  almost at the speed of light for a few minutes or hours, and when they return to earth, they discover that a very long period of time has passed. I know these are Sci-Fi movies, but obviously, this part is not made up.
Now, take this scenario for example. A person aboard some sort of spaceship is travelling close to the speed of light. They travel for a small period of time, maybe a few minutes. For this person, time is moving slower than for a person that is standing still. When this person was to stop, he would find that a long time had passed for everyone else.
Hypothetically,  If someone was to look at this person travelling  almost at the speed of light, wouldn't they see him travelling much slower than the speed of light? Because if time if passing slower to him, wouldn't he be moving in... slow motion...? 
So if it took him a few minutes to travel a very large distance, wouldn't the observer, for whom the time is passing slower, have time to observe the passage of the person moving at the speed of light?
What I don't understand is in this case, it would mean that to the observer, the person is not travelling  almost at the speed of light, but much slower. But to the person travelling  almost at the speed of light... well, they're travelling  almost at the speed of light.
Any help with this is appreciated. If someone can help me, please try to explain the answer in simple terms. If I have gotten one key idea of this wrong, please don't hesitate to correct me.  
Edit: I'm not just asking about the time dilation, I'm also asking about the velocity from different POV's.

A:

Hypothetically, If someone was to look at this person travelling almost at the speed of light, wouldn't they see him travelling much slower than the speed of light? Because if time if passing slower to him, wouldn't he be moving in... slow motion...?

Don’t forget that to the fast moving observer he is at rest. So it is you that is moving fast to him. His time dilation obviously does not affect your speed. The relative velocity is the same in each frame. He sees you moving as fast as you see him moving. 
Time dilation refers to something different. It refers to how long a physical process takes as described in different frames. Suppose that he is in his spaceship’s kitchen and wants to cook a soft boiled egg. His ship is moving at 0.866 c (time dilation factor = 2), and the water is already boiling. He drops the egg in as he passes the sun and takes it out as he passes the earth. In your frame it takes 9.2 minutes for him to move from the sun to the earth at 0.866 c, far past the optimum 6 minutes. In his frame it takes the earth 4.6 minutes (after passing the sun) to pass him at 0.866 c, substantially less than the optimum. So is the egg over cooked or under cooked? It turns out that it is undercooked. This is what is meant by time dilation. 
His time dilation does not slow down his velocity, it slows down physical processes like cooking an egg (or radioactive decay, or clock ticking, or heart beats, or ...)

