3-way switch light is on when both switches on or off, otherwise works as expected.
This is how 3-ways work

You have described what is utterly normal for 3-ways.   If you don't like opposite=off, do as brhans says in his answer that he's about to write.  And I'm with you, I do that all the time.   

Or go another way with a relay

You can't just use random relays out of the Mouser catalog.  However they make mains-wiring-listed relay modules legal for this, and they fit in a junction box knockout or inside a box.  

Use a latching relay.   This has two coils and a common.  Energize one coil, the relay throws on and stays.  Energize the other, the relay throws off and stays.   Energizing need be only momentary.  

You use these with a special momentary SPDT (in other words, a 3-way) switch that lives in the middle position until you push it up or down.  Now you can use the 3-way switch wiring to carry common and two coils.