Actually, Nicholson's film debut was in The Cry Baby Killer (1958) -- he played the lead juvenile delinquent.
DiCaprio was in 3 films before Gilbert Grape: Critters 3 (1991; Poison Ivy (1992); and This Boy's Life (1993).
(info courtesy of IMDB)
michael