Be scared, this is going to be long.
Fantasy and Science Fiction are part of the same overarching genre of speculative fiction. The division between the two is pretty fuzzy between science fantasy and fantasy with science ficiton elements. Fantasy is mostly defined as "has to happen in another world" while science fiction is defined as "could happen in our world". This is not a lock on the definition, but it serves in most cases.
Fantasy stories tend to have one to three elements: Fantastic characters (characters that have some aspect that makes him or her stand apart from the mundane), magic and the supernatural, and the other world (which could be mostly historical, enchanted (real world plus magic), alternate, invented world).
Horror does overlap some with fantasy and sci fi. However, horror is much more about powerlessness and the protagonists are "victims" of the horror; while science fiction/ fantasy is about empowering the protagonists to overcome the dramatic conflict.
Lots of different kinds of fantasy
historic fantasy
gothic fantasy Walpoles "The Castle of Otranto" 1764
horror fantasy (it is a messy category)
science fantasy, which includes futuristic fantasies (Pern, Darkover)
and more modern versions
Romantic Fantasy, Urban Fantasy, Magi-punk.
The roots of fantasy come from the ancient epochs when myth and faith were intertwined. You can go back to Gilgamesh as the first fantasy story. (And we complain about a couple of books, that was a huge set of 12 tablets). There were a number of Greek Fantasies (Odyssey and Iliad come most to mind, but there are others). There were the Roman version of the said, with other additions (Metamorphasis 12 AD) Beowulf is said to be the first English fantasy piece (though it is from a Norse source...) Speaking of Germanic and Norse sourcess, there was Der Ring des Nibelungen sometime in the 12th century and reproduced a couple of dozen times since. Ireland produced a huge amount of literature that mixed myth, fantasy, and faith, in the prechristian era. Dante's Divine Comedy is classic fantasy published in 1290.
There are also great works of fantasy in other lands, but I am not verse in the Indian or Chinese traditions well enough to really mention them in any other way that "they existed".
A personal favorite is Le Morte D'Arthur 1469. The tales of King Arthur create a new mythology of honor, chivalry, and courtly grace in the English of the period. The first published work about Robin Hood was an epic poem in 1510, but there had been folk tales since the 1160s. However, the tales of Arthur is what makes King Arthur loom in our cultural landscape and the history of fantasy.
King Arthur and related works such as the Fairy Queene and The Idylls of the King idealized certain aspects of English Chivalry and mythology. They did a number of a guy who wrote a huge number of fantasy stories in the late 1500s. What was his name? Oh yah. Shakespeare.
This man was prolific. Only a handful of his works survive to this day (If he wrote them at all, it could of been Lord Bacon or others). Those few works are enshrined as fine works in the English Language. Many of them are truly fantasy tales by modern estimations.
There are dozens of others before the Victorian age, but the highlights are: Milton, Swift, Walpole, Gothe, and so on. I wonder why fantasy is so panned by the of a literary bent. It would seem that many of The Greats wrote fantasy.
Victorians, boy were they prolific. Dumas wrote action adventure classics, but other works with fantasy elememnts (Coriscan brothers, Castle eppstien, The Vampire, and so on). Willliam Morris, Henry Haggard (KIng solomon's mines and Allan Quartermain, both fantasy and served as the foundation for pulps of the Indian Jones mold). And Americans of the same period also got into the act.. Mark Twain being the most famous. (Screwtap papers are hugely fun and Connecticut Yanke in King Arthur's Court.) Lord Dunsany was another famous one, who wrote a great deal about the faerie other world and invented so many fantasy world that he created the foundation for Lovecraft, Howard, CS Lewis, and Tolkien.
You know there are others in the related field of works that could be fantasy: let us not forget the people writing fairytales and folkelore, Lang and Grimms. Alice is considered a childrend story, but it is classic fantasy by Lewis Caroll. The Oz series is the same vein, by Frank Baum. Peter Pan and Mary Poppins were penned by people in this era, but I don't know by who.
If you are looking for Fantasy that might be more appealing to a 21st century personage, then you need things from the pulp era (1910 to 1940). Pulps are cheap magazines the churned out stories the way a meat grinder turns out hamburger. It is fast, it is ugly, but sometimes it is just wonderful. I am not going to identify indibidual works... just some authors of fantasy: Burroughs, Robert E Howard, HP Lovecraft, Clark Ashton Smith. These are The (fantasy) Greats of the period. They created all the cliches we know in fantasy today (besides those done by Tolkien), they just did them first.
Pre Tolkien a couple of great works do slip in between pulps and Tolkien.
The Once and Future King by White. Arthur strikes again. I think I prefer it to the original tales. Given a modern writer it resonates more with modern folk.
Gormenghast by Peake is obviously the inspiration for Castle Marrash at Skotos. Interesting indeed.
The Worm Ouroboros by Eddison. Interesting but hard, really hard, to read.
CS Lewis did Narnia. This tale shows that Christianity and Fantasy can live hand in hand. It expounds Christian ideals without being preachy or right wing... showing the error in many sects of Christianity. And it is coming to theatre near you soon.
In the 40s and 50s are LotR, science fiction ruled. However, pulish masters such as Leiber (Grey Mouser series), Pratt, and Sprague de Camp did a number of works.
In the 60s and 70s, fantasy took off again. Poul Anderson, Moorcock (favorite), Andrea Norton, Marion Zimmer Bradly, Jack Vance, Le Guin, McCaffrey (personal favorite) and Zalazny (recommended reading) round off the field. These people had a unique voice and did not follow Tolkien cliches.
In the 80s and 90s fantasy and science fiction took a back seat to horror and ran neck to neck.
Lots of Tolkien inspired fantsy spewed forth, in reaction to DnD and the Hobbit/ LotR animated movie a few years earlier.
Kurtz's Deryni nobels, set in a world similar to our medieval England, but with magic using people who came through gates.
Terry Brooks (Shannara) Yest this is Tolkienesk, but it is so darn good.
Pern series (mostly published in the 80s) by McCaffry
Chronicles of Thomas Covenant series by Donaldson is a classic. I prefer THe Mirror of Her Dreams and its partner A Man Rides Through, but I am in the minority.
Bradley did a lot of King Arthur inspired work with the women's view, The Mist of Avalon and all those.
Mercedes Lackey who produced dozens of book and defined an entire fantasy subgenre of Romantic Fantasy.
Charles DeLint who produced dozens of books and defined an entire fantasy subgenre, urban fantasy... classic fantasy creatures co-existing or visiting the modern realm.
There are more and others can add them, but there we go. A few minutes of Google, a few more searching my bookshelf, and the rest is just typing.
