Board Game Arena

My friends and I are getting bored of our usual games and looking for something new. Nothing that takes over an hour and nothing that relies on a huge degree of luck, some strategy should be involved, but nothing too complex.

Games we already play:
- Puerto Rico
- Carcassone
- Hanabi
- 7 Wonders
- Coloretto
- Sushi Go (rarely)
- For Sale (rarely)

Note: We did try Race for the Galaxy, but didn't like it.

Stone Age should fit in nicely with that group. Worker placement/resource management. There is a bit of luck involved with how well your workers gather the resources, but I wouldn't consider it a huge amount of luck.

For a short pure strategy game, I happen to like Quoridor too. That doesn't play at 3, though, just 4 (or 2). Unfortunately, it can have a slight kingmaking issue at 4 players.

I'm not sure of the time frame of Innovation. The first few games will probably be over an hour, but once everyone understands it the time should drop dramatically.

I highly recommend Lords of Xidit (better with 4p than 3p). It has a really nice theme, interesting mechanics and a really unique winning condition.
Moreover, you may like Kingdomino, Tokaido, Elfenland.

Also, I must have been really tired when I did my first list, to have forgotten a couple:

Takenoko is light and fun, and has a mechanic I enjoy of everyone having private goals accomplished on a common board.

Hawaii works well too. I'd recommend it at 4 over 3, but that's mostly my personal choice. Competition for activation spots is a major drive in the game.

And, Niagara. Fairly light like the others, and a lot of guessing/deducing what the other players will do.

(And support for the suggestions of Lords of Xidit, Tokkaido, and Elfenland, although Elfenland plays more interestingly with more players than fewer.)

Troyes and King's Guild are both good medium weight games that fit nicely in what you are looking for. (most comparable with Puerto Rico level difficulty)

Palaces of Carrara and Hawaii both work as well, slightly lighter than Puerto Rico but equal or heavier than the others...but rules are pretty simple in both.

Tokaido and Takenoko are slightly lighter (a little above Coloretto or Sushi Go) but would both fit.

Tea Time is a new game that is similar to Coloretto.

Seconding Tokaido, it is a nice game that plays deeper than what it looks and it plays best as 4p.
Also seconding Stone Age, it is a classic 4p gem.

Elfenland is worth mentioning here, it is easy to learn and has some interesting mechanics, plays well at 4p I think.