Yes, Kingdom Builder is a nice strategy game. It has replayability factors as well. The combination of different goals will have you adopting vastly differing strategies from game to game, but the card draws will force you to employ some clever tactics.
For deck-building, I suggest Mystic Vale. It has the same negative of drawing from the middle that Star Realms has (I guess; not familiar with Star Realms), but you choose from nine cards. There is another set of cards that you can buy from with more advanced "currency." What makes Mystic Vale especially interesting is that you always have 20 cards in your deck. You improve the cards rather than the deck. The push-your-luck factor is pretty nice too. It doesn't have as variability as Dominion though. Getting the expansion will help stave off potential stagnation. I've yet to really run into stagnation with this game, but I can see where it can happen.
I may suggest Roll for the Galaxy. I like it better than Race. Since you're not a fan of Race, I suggest you play with someone else's copy of Roll. It is very similar to Race, but you can mitigate the luck factor a bit better by reassigning dice. I like that mechanism. Perhaps Roll is missing the part about Race that turned sour for you.
Gauntlet of Fools is a goofy "dungeon crawl" with a push-your-luck element. You choose the best combination of adventurer and weapon, but the best ones will be fought over by players. To win an adventurer and his weapon, you have to bid using daring handicaps. So that adventurer combination may be way overpowered, but when he's juggling with one hand tied behind his back while hopping on one foot, he may do worse than the gimpiest of adventurers.
Room 25 has a cooperative aspect, but you can play competitive mode where you have four prisoners versus two guards. The issue being that nobody knows who is who (not even the guards know who the other may be). You're trapped in a high-tech maze and need to find Room 25. Not knowing what the other rooms are, you want to gingerly peek through doorways to see if they're safe, but a guard could lie about what he saw. Action economy is intentionally stunted, so you're racing against the clock. You can make clever use of combining the push action with a move action to propel someone through two spaces in one turn. Of course, that's assuming you trust the person to push you through the right door.
Sushi Go has a hand-drafting element. It's far simpler than 7 Wonders, which makes it a pretty good time filler. I've not played Sushi Go Party, but I understand it has additional cards that you swap in and out like modules. Plenty of screw-you moments as you see that someone is trying to get big points by getting three of a kind, and you keep denying him those cards.
Since you like maps, you could give Trains a try. The cardplay is pretty much a clone of Dominion. Their provinces don't score as many points, which is probably done intentionally in an attempt to place more focus on the game board. In Trains, you also use your cards to place pieces on a map. The inclusion of the board is a nice touch, but there are only two maps in the base game. The variability is lower in Trains since it's like playing just the base game of Dominion (somehow feels smaller). I like the idea, though I've never fully warmed up to Trains. I hear the expansion adds quite a bit.
I second Splendor. It's simple but engaging. The expansion sounds quite promising.
I really dig Evo. I've not played the new edition, and that's likely the version you would find out there. The original might be more accessible now that there's a new edition. The original is fun in that your dinosaurs control portions of the map, but as the climate changes, portions of the map become inhospitable to your dinosaurs. Your furry dinosaurs might be able to survive the mountains a little easier than your competitors, but when the earth tilts too far away from the sun, then no amount of fur can save them. Likewise, the beaches may burn up your dinosaurs regardless of parasols (yeah, they used parasols to indicate heat tolerance; that's my one big gripe). I really like the bidding mechanism for evolutions. This game is fun for me because you can adjust your play style based on the changing world.
And speaking of changing, Primordial Soup does this as well on a much smaller scale. You're living in a puddle. You can evolve your amoebas to process food more efficiently, to fight against the currents, or to eat other amoebas.
I am sure you may have already seen Power Grid, but if not, go check it out. Bidding, network-building, and screwing over your competitors by buying resources out from under them. I've only played the Power Grid card game once, but I liked it. It removes the map, but it still works out.