This is one of my pet hates.
Yes, you are right in that people must "get it" before they get to the door, preferably the clues would be so clear that we do not even notice that we notice. Doors are supposed to just work. We need to find what to do, and where to do it: the door should give clues. Feedback before the action so to speak.
The problem of course, is that the doors are designed already broken. This is at the bottom a question of an interaction design problem that we try to fix later by graphic design. Never a good solution, but sadly extremely common. The world is full of examples like this; some sort of operation and human input and action are needed, and the buttons, displays, feedback or lack thereof gets us stuck in the most mundane and stupid situations.
Doors come in a lot of different configurations; there are doors that swings both ways, automatic sliding doors, glass doors where there are no clues as to where the hinges are, revolving doors, handles to twist, handles to push down and then pull or push the door, bars across the door to push or pull (these often gives no clue as to which side the doors open). And most disconcerting: doors that swings in or out automatically. If you are a little fast there, you risk getting the door hitting you in the face.
Generally, doors swing out from a room or a building so as to not trap people in a fire. But this is not always the case.
- If possible, remove the handle from the side where pushing is to take
place.
- Red as a colour seems to me a bad idea: red = stop, no access. I am
not opposed to words or arrows as such, but colour coding red-green
is not a good idea.
- Personally, I think that images of what is not there would often do
the trick. You could simply draw a palm or pawprint on the
push-side, even if it has a handle.
- You could also take it further, and this would be an interesting
experiment: a fairly large, maybe humorous graphic of someone holding
a door open. The appropriate way for that side of the door. You would
give a clue and at the same time indicate gallantry :D

This, I think, however is the best solution:

At my local library, they have two double, sliding doors. Being enormously child friendly, the outer doors are decorated with childish drawings of animals with big goggly eyes. Curiously: these eyes point left, right and centre. People have trouble with where the doors open, and I think that if all goggly eyes pointed to the centre of sliding, problem would be solved. Brilliantly, at the moment they have trouble with the mechanics of the outer door, and there is a notice "if the door is slow/stuck, help by pulling". There is nothing to pull with. So you get people stuck, desperately trying to pull with sticky palms. Architects FTW.
There is a classic story from Donald Norman, where a friend got stuck between double glass doors, as there was no intuitive, logic or informative way of getting out. He expands on this quite a bit in the book The design of everyday things
Here is the basic story:
My friend pushed on the side of one of the leftmost pair of outer
doors. It swung inward, and he entered the building.
Then, before he could get to the next row of doors, he was distracted
and turned around for an instant. He didn't realise it at the time,
but he had moved slightly to the right. So when he came to the next
door and pushed it, nothing happened. "Hmm,"he thought, "must be
locked."So he pushed the side of the adjacent door. Nothing. Puzzled,
my friend decided to go outside again. He turned around and pushed
against the side of a door. Nothing. He pushed the adjacent door.
Nothing. The door he had just entered no longer worked.
He turned around once more and tried the inside doors again. Nothing.
Concern, then mild panic. He was trapped! Just then, a group of
people on the other side of the entranceway (to my friend's right)
passed easily through both sets of doors. My friend hurried over to
follow their path.