This is how I would do it.
Don't have one player host a game – have players search each other out and find a neutral virtual table. You can suggest a game with a friend, but the usual way of getting a game is with automatch. You state how many players you want in the game (as an interval). There could be other stuff you could specify as well, like point-counter allowed or not, if special modes like veto mode should be used if it will be implemented, etc.
The automatch facility sets players on a table matching them according to rating. How near each other they have to be depends on what players are available right then.
When the players are seated a random kingdom is created out of the union of all cards the players have. (Like they could do if they met afk and combined what they had.) All three players having Smithy doesn't mean that it gets a higher probability of appearing than Governor that only one player has – every possible card gets the same probability.
You wouldn't have to bring all your cards to the game. If you hate that Possession, move it to the cards-I-keep-at-home pile. (Avoid people not buying a set because there's one card there they don't want to get in their games as often.) You're not safe though – someone else might have brought it. Probably only few players will bother taking away cards they've bought like that, but it can be very useful for some.
You would get a game a lot quicker than now, where players have to run around among all ongoing games trying to find someone else who wants to play. I think players getting a game a lot quicker would be good. I understand that they might think that it's good if it's annoying to be there before you buy cards. "This sucks. I'd better buy some cards so it stops sucking." But my sincere guess is that it would work better with "Hey, this is great! I'll buy some cards so it becomes even better." Because the only way to surely avoid all-basic games is to get some cards yourself. As a beginner you would meet other beginners. Often this will be all-basic games. Then now and then you'll see other cards appearing, and you might get favorites among them. "Hey, I want Colony and Platina in my games more often!" This gradual introduction of cards will be better than how Isotropic was, where it was a bit daunting to get everything at once as a beginner.
During or after a game you can tell the server that you don't like to play that player and automatch will avoid matching you. They don't get to know that. They aren't put on a list of players to avoid for anyone. It's just your decision, and could be for any reason. There are some drawbacks with this, but it needs to be done. You shouldn't be forced to play games you don't like. Maybe it is because they are rude, or too slow for you, or maybe it's your ex-boyfriend that you don't want to interact with. It doesn't matter. Yes, people without cards can and will use that to avoid other players without cards as well. So let them. That won't be worse than it is now.