However, I've seen questions from native speakers like this one that suggest that the other meaning has eclipsed the literal meaning. Is this true? Is it best avoided if you're referring to a generic first experience? And if so, what expressions are good substitutes for it? I believe that 初土俵 or 初舞台 (mentioned in the linked question) would only be suitable for a début (i.e. someone's first entry into the public sphere).
When it is obvious what it is about, using 初体験 doesn't necessarily carry the other meaning.
For example, if you are eating Natto for the first time, you could say 初体験です and it doesn't sound weird (to me). An alternative is simply using 初めて食べます (or other verbs) or using 初X (初納豆です in this case) would work as well.
That said, it is to some extent true that 初体験 has that connotation and perhaps tends to be avoided. In contrast to the above, when speaking of eating Natto, it would be odd to say 初体験はいつですか in order to ask when the listener ate Natto for the first time (the sentence would be almost always understood in the other meaning).
Also, typically in TV, 初体験 is used intentionally to (kind of) mislead the audience. For example, captions* like あの女優が初体験 are used when an actress does something for the first time; of course, the audience wouldn't really expect the other meaning, but it is kind of double-meaning and probably has an eye-catching effect. In this sense, 初体験 defaults to the other meaning today.
(*captions: I don't know much about how things are abroad, but in Japanese TV programs, commercials are inserted about every 10-15 mins and before a commercial starts, there are captions to keep the audience for what comes next.)