If a man who was a firstborn in his Gentile family converts to Judaism, must he redeem himself after becoming a Jew? I know that the general rule is that a Ger is considered a newborn child, but would that mean that he essentially has a new, non-firstborn Halachic rebirth, or does the original literal first birth still apply to him?
The ger, not having been born of a Jewish mother, is not subject to redemption at all and therefore isn't required to do it for himself.
This article from OU outlines various cases of who does or doesn't get redeemed. To summarize:
If the father is a kohein or levi or the mother is a daughter of a kohein, there are special cases. (That's not your question, so I'm skipping these.)
If a boy is born from a non-Jewish father and a Jewish mother (with some kohein-related exceptions), the boy must be redeemed. Even though it's the (Jewish) father who's obligated in pidyon haben, the father being non-Jewish here doesn't exclude the boy. There are various opinions about who does it in this case; some say the beit din and some say the boy himself when he reaches bar mitzvah. (Perhaps you are reasoning from this case to the ger who becomes bar mitzvah upon conversion.)
A baal teshuva who doesn't know his lineage should do it out of doubt but without a b'racha.
Nowhere on this list does the case of a non-Jewish mother appear. A ger, by definition, is the child of a non-Jewish mother.
The Halachipedia article has a little more detail but also does not talk about the case of a non-Jewish mother. It also notes that in the case where the father doesn't redeem, the obligation transfers from the father to the son at bar mitzvah. (They cite Shulchan Aruch YD 305:15, Kitzur Shulchan Aruch 164:8, and Yalkut Yosef Sova Semachot vol. 2 pg. 224.) The ger's father was never obligated and so there is nothing to transfer.