What does "improvisation" mean? In the first place, every performance takes place in time, and will vary from any other performance. Someone playing the melody of "Stardust" pretty much "as written" will still be improvising the phrasing, tempo, etc...
Note, too, that we are usually not comparing a performance against a written score at all, but against our memory and experience of other performances. The zero degree of improvisation is simply performance itself, insofar as performance can never be rote repetition, even if heavily rehearsed.
The next degree of improvisation would be embellishment, ornamentation, added to a relatively straight rendering of the melody. This is improvisation around the edges. Let's call this improvisation at the first degree.
The second degree would be modification and paraphrase. The melody is still recognizable in its overall shape, but some notes have been changed, or whole phrases substituted. You'll notice too that these stages of improvisation are often sequential: an embellished statement of the "head" of a tune will be followed by an improvised paraphrase.
Thematic improvisation is the development of melodic ideas and motifs, leaving behind the countours of the original melody. Harmonically based improvisation is "blowing over the changes," playing mostly arpeggiated patterns and formulas. Some writers refer to horizontal (melodic) improvisation vs. vertical (harmonic) improvisation. The melodic tradition is that of Lester Young, Sonny Rollins, and Ornette Coleman. The harmonic tradition reaches its apogee in Coleman Hawkins and John Coltrane. When Coltrane plays a ballad, however, you will see that he uses mostly direct, unimprovised statement and harmonically based embellishments.
Another relevant distinction is between players who are more formulaic, playing a pre-existing set of formulas, and those who are purer improvisers, avoiding easy or pre-established solutions. Improvisation is a continuum between direct statement of pre-existing material and truly free invention.
To state that improvisation is essential to jazz is rather obvious, but does not answer the question of what improvisation really is. I see it as a range of performative practices that do not always invariably entail the super-inventive spontaneous composition of romantic stereotype. There can be performances with a high degree of jazz performativity that don't have a whole lot of improvisation per se. Take Mingus's "Goodbye Pork Pie Hat," for example, or much of Ellington's music, or Coltrane's "Naima."
That being said, the truly great improvisers stand out, precisely because not all "great" jazz musicians are great as improvisers per se.