Intuitively, how can the work done on an object be equal to zero? To my understanding the work done on an object is defined mathematically as:
$$W = \vec{F}\cdot\vec{S}=|\vec{F}||\vec{S}|cos\theta$$
This, I understand. My problem is that I don't understand that if the angle $\theta$ is 90 degrees how can the work done by $\vec{F}$ on the object is zero. For example; say you have a particle and the direction of the displacement is directly to the right, and you also have a force vector acting on the particle that is straight up(like the normal force on a box that is standing on a flat surface). How is it possible that the force vector is not doing any work? Must the particle not take a different route because of the force vector acting upward on the particle, like if you add the vectors together?
There has to be something wrong with my reasoning, but what is it?
 A: Because it's not any work, but the work done by a force that produces a displacement. 
In the scenario you describe, somehow that force is not doing any work on the particle. This could be because the particle is restricted by another force to not go perpendicular and then the sum of forces in the perpendicular direction is zero.
In the second scenario, with the box and the normal force, it's the same. That force doesn't do any work since in the direction of that force there is zero movement. Which is analogous to say that the cosine of the angle between the displacement and such force is 90°.
A: I like to think about it in the context of the Lorentz Force, i.e. the force on a charged particle by an electric and a magnetic field. The first time you check by yourself that the magnetic force does no work, it is puzzling.
$$\vec F = \vec F_{electric} + \vec F_{magnetic} = (q\vec E) + (q\vec v \times \vec B) $$
The force due to the electric field $q\vec E$ is easy to understand. But, since the result of the cross product $q\vec v \times \vec B$ is always perpendicular to  the velocity $\vec v$, then the force due to the magnetic field does zero work (the instantaneous displacement $d \vec r$ is parallel to $\vec v$, therefore $dW = \vec F_{magnetic} d \vec r = 0$).
A good way for students to intuitively understand this, consists on thinking of the charged particle as a car. Then, the electric force is the result of the forward push due to the engine, and the magnetic force is simply the result of the driver inside the car effortlessly turning the steering wheel. That may give you some intuition about it, specially if you consider a vehicle with rear-wheel drive.
No matter how heavy a car or a lorry may be, it is nearly effortless for an old lady to turn the wheel to the right or left, and the whole vehicle will change its trajectory. The work is done by the petrol engine pushing forward. Turning the steering wheel is effortless, but it has a deep impact on the trajectory of the vehicle (the electromechanical steering boost mechanism is there only to counteract internal friction forces).

How can you effortlessly change the trajectory of a heavy lorry? Because the reaction on the turned wheels results in a force that is perpendicular to the movement of the vehicle, therefore it does zero work: it is effortless for the driver. This is easier to understand, as said, if you think on a rear-wheel drive car, so that the front wheels play a passive role in the "push" done by the engine.
A: When you say work done, you mean to say work done by a force. In science, regardless of the amount of force you apply, if you don't produce a displacement, you aren't doing any work.
Now consider a force acting on an object, but the object moves in a direction perpendicular to the force. You can safely say that the force is not the cause of the motion of the object. This means that the work done by the force you're looking at is zero.
A: Particle will take different route - if the angle $\theta$ is always 90 degrees and force has always the same absolute value the particle will move in a circle.
This happens to charged particles moving in a magnetic field.
Direction of movement will change but absolute value of velocity will always be the same.
A: You just can't add them like that. They are after all,different physical quantities. You may say the upward force is enough to change the particle's route, but it has its mg, right?
Another "intuitive" example is just the one you gave-a box on the floor. It does not jump? :-)

Another thing, if due to any force, displacement occurs which is not perpendicular, work is done. In what you said, lets just say particle changes its path, then WORK IS DONE because the angle changes and intuitively because the force causes the displacement. In whatever example you'll come across with work zero but force causing displacement, displacement is always perpendicular to the force. (E.g. centripetal force).

Please reply because I think I explained well enough.
A: The force is perpendicular to the prescribed path then it does no work, as it is a reaction force. A force that is there to enforce the constraint that the particle can only move to the right.
It might be easier to understand it terms of power, which is $P = \vec{F} \cdot \vec{v} $ with $\cdot$ the dot product. Only the components of force along the direction of motion affect the motion (and thus add energy) to the system. 
A: Your reasoning is alright.

This, I understand. My problem is that I don't understand that if the angle θ is 90 degrees how can the work done by F⃗  on the object is zero. For example; say you have a particle and the direction of the displacement is directly to the right, and you also have a force vector acting on the particle that is straight up(like the normal force on a box that is standing on a flat surface).

Absolutely correct: If the displacement and force are perpendicular then there is no work being done by the force. That is, the force does not change the energy of the system it is acting upon.

How is it possible that the force vector is not doing any work?

"Work" is a transfer of energy. Typically you can say it is a transfer in to or out of the kinetic energy of a system. If a force acts along the direction of motion it adds to the kinetic energy, if oppositely directed, then kinetic energy is decreasing, if acting perpendicular, then no change in kinetic energy, and hence by definition, no work being done.

Must the particle not take a different route because of the force vector acting upward on the particle, like if you add the vectors together?

Again, your reasoning is essentially correct. The object will take a different route, that is, change direction (if there is no counterbalancing force to this). If so then the force will be then acting centripetally, though in doing so the force will not have any component acting along or against the direction of motion and hence not affect the object's kinetic energy, and then again by definition, do no work.
