I'd just start at the beginning with the Collection. Pretty sure the stories connect but even if they don't, seeing the mechanics evolve backwards or out of order can be annoying. Like you start with 4 and then when you play 2 or something and a mechanic isn't there that was nice, it kinda kills the experience. Starting from the earliest point and working up makes it feel way better as they begin to nail down and improve things.
Similarly, 2 was my first Uncharted, which I played partway through at a friend's. When I got my own PS3 I decided to start back at 1 and found it did a much better job of teaching me how to play the game than 2 did. When I went back to 2 after finishing 1, everything I had trouble with was so much easier, and it was really need to see the jump in graphics between the games.
Yeah, like others have said, play them in order starting with 1. If you play them backwards or out of order, you aren't very likely to finish the first one, maybe the second, the first is kind of a slog, but worth playing. This way they just get better each time you go to the next
The Nathan Drake Collection. Uncharted 1 is a bit rough around the edges, but I would recommend going in order of release either way.
Enjoy, those are wonderful games! (I might be slightly biased, Uncharted is probably my favourite video game series tbh)