I'm not sure if there is any board size that's particularly good at teaching new players the basics. For new players this game feels essentially completely random. Knowledge of two certain things is what turns it from a game that feels completely random to a strategic game.
The first is the "all but 2"-trick and the second is the chain-rule
Let me try to explain both of those using two positions on the 3x3 board:

This (left) is a position with 1 chain that has 14 lines played. Because of that it's the turn of player 1 who can play anywhere into the long chain (middle). And then player 2 takes all boxes of that chain (right).

In this position on the other hand there is two chains and only 13 lines played in total (1st position).
Then its the turn of player 2 and they can play into either of the two chains, but will likely pick the shorter one (2nd position).
Player 1 can now take that box at the bottom (3rd position) and its their move again.
Now this is where the magic happens: Instead of taking two more boxes player 1 instead plays at the top. This is the "all but 2"-trick. (4th position)
Player 2 now gets two boxes but is forced to play into the chain of length 6. (5th position)
And player 1 takes the remaining 6 boxes, thereby winning the game. (6th position)
So there is two things to take away from that. Firstly, there is that "all but 2"-trick that let's you gift two boxes to your opponent in exchange for forcing them to play into the next chain. This basically means that once your opponent has played into one chain you can get all except two boxes of every remaining chain. The very last chain you can even take completely.
Then secondly, the thing that ultimately decides the winner is the amount of chains at the end. The top picture has that position with one chain and that causes player 2 to get all of the boxes, whereas the bottom picture starts with a position that has two chains and as a result of that it's player 1 who wins. That's what the chain rule is about: One player wants an even amount of chains, while the other wants an odd number of chains.
Once you know the chain-rule the game turns from a game where you just play moves randomly into one where you try to form a specific amount of chains and then it's about dividing the board into a desirable amount of areas and do certain types of shaping.
Anyway, back to board sizes.
I think if there is a board size that does a better job at teaching chain-rule and "all but 2"-trick than 5x5, then that would be a better board size for beginners than 5x5.
First there is 3x3. This board is actually so small that it's quite difficult to squeeze any number of chains other than 1 onto the board. So the vast majority of the time I would expect new players to just build one chain with completely random moves and then the second player just wins by taking that resulting chain at the end without understanding why they actually won. I also just generally don't like the idea of giving two competing minds a board where one player just wins 6-3 with optimal play from both sides. So I'm not a fan of 3x3.
3x5 on the other hand I think may be good. This one I would consider an actual game. My guess would be that with optimal play it's a 7-8 victory for player 2, but it's not trivial and I'm not sure I'm even correct. For new players I think this is actually quite a big size already and I would assume that most of the time in a game between new players it would result in 2 chains, which, contrary to my own assessment of who should win, would result in a player 1 victory, and also does provide an opportunity for the "all but 2"-trick to be used. In order for someone to master playing this size as player 2 they would have to learn important concepts like sacrificing in order to win with the chain rule.
I think overall 3x5 does make for a good size for beginners, I don't know if it's better than to just let people play on 5x5 from the get-go though.
I think much more valuable than just providing a beginner friendly size would be to actually provide some kind of tutorial that explains the "all but 2"-trick and chain rule. I think while people may discover the "all but 2"-trick on their own it's going to be very difficult for people to discover the chain-rule. In my opinion these 2 things should be explained to people somewhere on the site.