Jeebs in the animated series is Billy West, except for a few times that Tony Shaloub reprises the role.
The Other Marty: Famke Janssen was originally cast as Serleena, and completed some scenes before dropping out due to a death in the family, with the role subsequently recast with Lara Flynn Boyle.
Suspiciously Similar Song: The theme for the cartoon series carries the first few beats of Will Smith's eponymous "Men In Black" as part of its main theme, but ditches the rest of the song in favor of a instrumental hip-hop composition.
The scene where the alien that Kay killed in the beginning of the film transformed was not originally planned. The creators added it in because they realized that most people would have sympathized with the alien had he died as is, and wanted to ensure no sympathy was to be gained for the alien prior to being killed.
Will Smith's line "It just be rainin' black people in New York!" was improvised but so hilarious that they decided to leave it in.
As was his line in the sequel when showing Kay the car: "It used to come with a black man, but it kept getting pulled over". Apparently they reused it so much that he soon became sick of it.
In fact, a lot of the lines in the original film were this. Tommy Lee Jones didn't like the script and made up most of his dialogue on the spot, with Will Smith trying to keep up. It was hilarious enough that Barry Sonnenfeld just didn't care and threw it ALL in. And the movie ended up being praised for its witty dialogue, in case you needed more proof how awesome Tommy Lee Jones is.
In MIB II, rapper Biz Markie was visiting Will Smith on the set and they were beatboxing to each other. Sonnenfeld saw this, loved it, put Markie in as an alien in the post office scene, and added the part where J speaks to him in his native language (which was really just their beatbox routine).
According to the book The Man Behind the Mask, Michael Jackson would have appeared in the sequel for free...if Will Smith were dropped from the film so he could be the protagonist. He couldn't convince Sony's higher-ups that this was a good idea, hence the cameo instead.
Bruce Campbell was the one originally in mind to play the exterminator, but he turned it down to appear in some TV movie that even some of his more hardcore fans haven't heard of.
The sequel would've used the World Trade Center in some way, but then September 11th happened.
Originally, there were going to be two alien ships looming over the Earth, demanding the return of the galaxy: the Arquillian ship, and a Baltian ship (Rosenberg was originally a Baltian in the script). Edgar came to Earth to deliberately start a war between the two races, said to be negotiating peace, so he can feed off the resulting war. The initial volley is compared to two gunslingers using a giant rock as cover. Eventually, they decided the Baltians were not necessary to the plot, so some work was done in post-production (dubbing the aliens' conversation into "alienspeak", for one), and long story short, Rosenberg became an Arquillian.
Yeardley Smith originally auditioned for the part of O in the third movie.