Me/gender history/tldr
While I knew since about age 5 that there was something odd about me that had to do with gender (a word I didn't learn until years later, when it came as something of a relief to learn that there was in fact a general word for gender that wasn't gender-specific), there were a lot of clues that threw me off the trail of figuring out that my gender had been misidentified (because it didn't match my body).
For example: while I preferred playing with girls, I didn't like playing "girly" things like dolls or dress-up or "house". I didn't like most boy things either, but I did like building stuff and electronics and computers and other stuff that was heavily male-tagged. I especially wasn't drawn to feminine dress.
I'd always been drawn to tomboys, and girls dressing in practical / gender-neutral clothing and doing the sorts of male-tagged things I liked doing. So I was always just kind of mystified by the few examples of "transsexuals" I came across in the media. Why would you want to dress up like a woman? Why do women like to dress as women? It didn't compute, and I certainly couldn't identify with it.
There was also the problem that I believed, based on the "gender is entirely culturally constructed" theory that was popular at the time, that it was logically impossible to be a different gender than what you appear to be. If gender is entirely learned behavior, then how can you have learned to be the gender that isn't what you appear to be? I kept trying to figure out how there might have been some element in my upbringing or schooling that might have caused this, but basically it didn't make any sense...
...until I came across more up-to-date information on the internet, in 2000, which explained that actually gender identity is essentially hard-wired (it's just certain aspects of gendered *behavior* that are taught) and then everything suddenly clicked into place and I had the classic "oh! I'm a girl!" moment.