First, if you have been playing a lot D&D, you might want to run something other than fantasy first. That said, there are a lot of good setting choices for fantasy depending upon what you want.
Beasts and Barbarians (GRAmel): already mentioned
Iron Dynasty (Gun Metal Games):already mentioned
Hellfrost (Triple Ace Games): However, you will not need one additional book, but 2: The Players Guide and the Bestiary
Sundered Skies (Triple Ace Games): Post Cataclysmic Fantasy with floating islands and sky pirates
Sherwood: The Legend of Robin Hood (Battlefield Press): by the author who did the Robin Hood for d20 article in Dragon (note: there are two versions: one for d20 and one for Savage Worlds)
Outside of fantasy, you also have a lot of good things:
Agents of Oblivion (Reality Blurs) traditional spies to X-Files
Darwin's World (RPGObjects): the d20 Apocalypse game now in Savage Worlds (Note: 2 books)
Gaslight (Battlefield Press) : Urban Victorian Fantasy
Interface Zero (Gun Metal Games): Cyberpunk
Mars: Savage Edition (Adamant Entertaiment) Savage Worlds version of the d20Modern supplement abot Planetary Romance along the lines Edgar Rice Burroughs Barsoom.
Pirates of the Spanish Main (PEG): Running pirates in a licensed game
Realms of Cthulhu (Reality Blurs) : offers for different styles of Cthulu. Demonstrates that Savage Worlds does not have to be "pulp" in the sense of high action.
Thrilling Tales 2e (Adamant Entertainment): The Savage Worlds version of the d20Modern toolkit/sourcebook for the Pulp genre.
War of the Dead (Daring Entertainment) : 52 adventures in 4 books (13 adventures per book) as the setting for the events leading to a zombie apocalypse world. Starts from the initial outbreak and leads up to a campaign setting that is supposed to follow the four books.
You also have some free games from Triple Ace Games
Daring Tales of Adventure: A small pulp game that is supported by pay for supplements
Daring Tales of the Space Lanes : as Daring Tales of Adventure, but space
Daring Tales of the Sprawl: as Daring Tales of Adventure, but cyberpunk
You also have
free one sheets and supplements on the PEG site including:
Crime City Moscow Connection which is a free genre supplement from PEG designed to show how Savage Worlds can be altered to be Gritty. it is located on the page linked above. Scroll down.