Alright, I think I've made up my mind eventually, thanks to everybody who has helped here! Thanks for your time guys!
So I'll have a lobby server which will be ran on localhost on some specially designed for server machine. Do you think that for about 100$ I could buy a machine for lobby server that should handle 100 people online?
Lobby server will handle all the match making and after a match has been created and started one of players will host the game to others. Here's one more question: Should the server be implemented in the same .exe as client or it should be a separate program? or it doesn't matter at all?
And if my game occurs to be so cool that hackers will get interested then I'll think about some secure remote hosting ^^

How you separate the client and server is up to you, personally i'd put the server in its own library/class and build it into the client .exe aswell (This makes it fairly straightforward to move it out to a separate binary if you want dedicated servers later on).

The lobby server shouldn't really have to care about how many players you got online, it only has to work when players are trying to find a match. (The longer each game lasts the more players your lobby will be able to handle), $100 is pretty hard to get anything for these days, you might be able to find an old used machine at that price though. (If you buy new hardware it becomes very difficult to get a working system for less than $200-$300) (If the computer runs, is capable of running a decent server OS and can connect to the internet its good enough for a small lobby)

Alright, I think I've made up my mind eventually, thanks to everybody who has helped here! Thanks for your time guys!
So I'll have a lobby server which will be ran on localhost on some specially designed for server machine. Do you think that for about 100$ I could buy a machine for lobby server that should handle 100 people online?
Lobby server will handle all the match making and after a match has been created and started one of players will host the game to others. Here's one more question: Should the server be implemented in the same .exe as client or it should be a separate program? or it doesn't matter at all?
And if my game occurs to be so cool that hackers will get interested then I'll think about some secure remote hosting ^^

How you separate the client and server is up to you, personally i'd put the server in its own library/class and build it into the client .exe aswell (This makes it fairly straightforward to move it out to a separate binary if you want dedicated servers later on).

The lobby server shouldn't really have to care about how many players you got online, it only has to work when players are trying to find a match. (The longer each game lasts the more players your lobby will be able to handle), $100 is pretty hard to get anything for these days, you might be able to find an old used machine at that price though. (If you buy new hardware it becomes very difficult to get a working system for less than $200-$300)