One of them is essential
You need either the largest army, longest road, or a lotta luck to win. While you should probably not start building them right away, you should figure out early in the game which one you are eventually going to shoot for, and how you will do it.
The size of the board and number of players could influence your decision. For example, it could take a different strategy to get the longest road on a crowded board, compared to a wide-open board. On a wide-open board, the player who can pump out the most roads can probably will get it, meaning it probably easier playing with a wood-brick strategy.
On a crowded board, the number of hex sides is the determining factor, and the player who can get to those faster will probably get it. The nod could still go to the wood-brick player here, as they can usually get to areas faster, but other factors might be more important in this situation, such as the starting location. However, this doesn't mean that the longest road is "harder" to get on a crowded board; after all, only one person can get it on any board. It just takes a different approach.
Be a contrarian
Note that the longest road and largest army are worth more if the other players aren't trying for them. The more roads/knights that you have to buy, the worse the investment. This could be more of a factor in determining which one to go for than the type of board and number of players. This means it might actually be preferable to go for the one that you normally would not, if there is going to be a lot of competition (for example, longest road when you are playing an Ore/Grain strategy).
Avoid too many side trips
If going for the longest road, don't make too many "side trips" with your roads. You only have 15 in the basic game. Remember, if you are the first person to get a road 15 in length, it cannot be taken away from you (unless someone splits it, as shown below).
This is much less important in Seefahrers, when the longest road could theoretically be 30 long (it includes ships). This also means that getting the longest road in a Seefahrers scenario can be much more costly if a race develops, a factor to consider when deciding between getting the Longest Road or Largest Army.
Doing the splits can make you uncomfortable
Remember if an opponent builds a settlement in the middle of your road network, your routes are split in two for purposes of determining longest trade route. (Matt Gardner ) Also remember that no one can split your ship lines.
If you know you are not going for longest road, then building settlements off triangle forks saves you having to build two roads for each settlement, and instead allows to you build three roads (instead of four) to get to two settlements.