Here are some notes (actually, a slightly edited email response) I just wrote up on the topic before this question was asked here, but I'll try to organize it later. All halachic sources are found Orach Chaim 489:
I wasn't sure if that Halachic rule would overpower the Chiyuv to
count immediately because of concerns for "Mitzvah Haba'ah
Leyadcha...", "Zerizin Makdimin" and "Temimos" etc.
It turns out that the Biur Halacha (s.v. Achar) quotes the Chok
Ya'akov who applies the rule of Tadir here, and says that one should
wait for Ma'ariv before counting. The Piskei Teshuvos (Note Gimmel)
takes this further and adds that you should count it Betzibbur, which
would be another reason to wait for Ma'ariv later to count.
However, the Magen Avraham (Note Zayin) says that one may count by
themselves even before Ma'ariv, and he does not seem to qualify it as
Bedi'eved. He, nor any of the commentaries I saw, object on the basis
of Tadir. The Aruch Hashulchan (Se'if Yud) cites this Lehalacha and
says that it is the "Derech Ha'olam" to count after Ma'ariv, but that
it is fine to count before as well. The same Bi'ur Halacha quoted
earlier cites the Mor Uketzi'a who supports this as well.
If we accept that there is a Chiyuv to count Betzibbur and/or follow
those Poskim who apply "Tadir...", you could make the argument that
one does not have to count right away. However, if we reject that
view, and follow the Magen Avraham/Aruch Hashulchan, it is hard to see
why one should delay counting the Omer until after Ma'ariv.
(I would note that the question of Tadir is only applicable when both
are in front of you and can be done now. If I am waiting for a minyan
to daven later, and have a shomer/alarm reminding me of it, but there
is a Chiyuv Sefirah now, I'm not sure anyone would say that Tadir
applies. Even the Bi'ur Halacha and Chok Ya'akov only say it where the
person is in shul davening Ma'ariv. Perhaps this is why the Piskei
Teshuvos is so strong about the necessity to count Betzibbur...?)
The Igros Moshe you cited (OC 4:99) does indeed side with the
opinion that Tadir applies here, but that still may only be
preferable when one has a Minyan Kavua and isn't concerned that they
will miss Ma'ariv (from a Halachic standpoint). Additionally, Rav
Moshe opposes all of the poskim I noted above, which are mainstream
and accepted, in addition to the Taz and the Bi'ur Halacha that he
himself points out seem to oppose him.
Practically speaking, I discussed this with a Posek, who indicated that common Psak was in fact to count before Ma'ariv in such a
situation. I also heard in the name of Rav Schachter that Tadir
applies only when both Mitzvos can be done optimally at that point in
time, and that he applied it to this situation to say that one should
count first and daven later, since it is not optimal to daven Ma'ariv now.
On the other hand, Rav Moshe is a pretty reliable source himself...