We've enjoyed seeing the US Presidents and other real life celebrities in the New New York Head Museum. Who was/were the first fictional TV character(s) from a different show given a nod as labeled head jars on Futurama? The Star Trek cast appeared as actors, not characters. I'm looking for labeled names on the headjars of fictional characters.
Having had a flick through the head jar episodes, Space Pilot 3000 does not have any named fictional characters. There are a lot of heads without nameplates present.
The earliest I can definitely confirm a fictional head appears is in All The Presidents' Heads (Season 6, Episode 20) - Sharon Anders is the first to appear at 2:46 into the episode. Several more appear later in that episode, including (later) Amelia Pond (the first fictional TV character, as per your question, at 3:11) and Inara Serra (4:04).
The only confirmable fictional un-nameplated head in an earlier episode that I've found is Eric Cartman, who was in Bender's Big Score.
The infosphere lists five fictional characters to have appeared in the Head Museum, the first non-Groening character seems to be the head of Eric Cartman appearing in the first film, while the very first fictional character to appear in Futurama alltogether is the head of Apu Nahasapeemapetilon, who apparently already appears in the very first episode (Space Pilot 3000).
I highly doubt that a head is seen previously, outside the head museum, as the heads in jars are introduced when Fry enters the museum, and they only visit it once during that episode.