He didn't choose them at random because he didn't encounter them at random. Each time, his prior recruits take him to see the next one. And while it's not really made clear in the movie, his choices do seem to line up nicely with the traditional roles of the Horsemen.
The order in which Apocalypse acquires his Horsemen is:
- Storm, whom he randomly encounters on the streets in Cairo. En Sabah Nur makes her a Horsemen and tells her he needs more.
- Storm takes him to see Caliban -- a guy who helps "traffick" mutants -- where she assumes there will be plenty to pick from. This is the same guy that helped get Kurt Wagner into the US. Here, En Sabah Nur recruits Psylocke.
- Psylocke knows the whereabouts of plenty of mutants, since she's Caliban's assistant. She picks Angel as the next target, and takes En Sabah Nur to see Angel and recruit him.
- They then see Magneto on the news, and he's a famously powerful mutant, so En Sabah Nur hunts him down in Poland to recruit him.
So his first recruit was, indeed, random, but afterwards, he clearly selects his recruits carefully. He even ignores one (Caliban) in favor of another (Psylocke), and tracks two of them down where they were and recruited them.
How much of a connection there is to the Biblical Horsemen isn't clear, but there are at least some hints that it was intentional. In the source comics, there are many different mutants playing the Horsemen, but in most cases it's obvious which is which. In this movie, it's less obvious, but the intention appears to be:
- Magneto - Horseman of War. This one's obvious, because he wants to start a war against humans.
- Angel - Horseman of Death. He's been the Horsemen of Death in the comics, playing on the "Angel or Death" motif that's common in fiction and mythology.
- Storm - Horseman of Famine. She has had this role in at least one of the X-Men cartoons. The connection here being that terrible, violent storms can cause severe damage to crops, livestock, etc. and lead to famine.
- Psylocke - Horseman of Pestilence. This one is the only one that doesn't really seem to make sense. It's especially odd, since Caliban is a Horseman of Pestilence in the comics, and his power to track other mutants could be used to "spread" Apocalypse's influence. Psylocke was a Horseman in the comics, but she was Death. (It appears that Psylocke was a very late choice for a Horseman (thanks @armfoot), so that may explain why she seems unfit for that role.)