As far as I know, those two are set in the same world, but tell a different story, is that correct? I know that Elantris came out first, but it's not available for Kindle and Warbreaker is freely available from the author's website. I have never read anything by Brandon Sanderson and while this guy is writing the ending of the Wheel of Time series which I loved years ago, I'd like to get to know his style. Can I read Warbreaker first? Will I miss on something? Can it be treated as a standalone novel even if I don't know the other books in the same setting?
As far as I have noticed, Elantris and Warbreaker are completely independent; there are no connections between their plots. They are, or might as well be, in completely different worlds. Both are also unconnected to the Mistborn trilogy.
To give a fuller answer than that Kevin Reid's,
Although they are set in different worlds, it is worth noting that they, like almost all of Sandersons solo works (Alcatraz excepted), take place in the same 'meta-cosmology'.
An example of this, is a character who shows up repeatedly in the background of them. Way of Kings sheds a bit more light on this for the observant reader, so in that sense it would be worth reading Way of Kings after the rest of his works, just to see if you can spot the shared character.
So although Warbreaker and Elantris don't impact on each other plotwise, it would be worth noting that there is a background story hinted at in these, and will be dealt with slightly more overtly in the Stormlight Archive (book 1 of which is Way of Kings).
I'm hardly the most well-read sci-fi/fantasy reader, but Elantris feels less realistic to me. If I were reading the two books without knowing anything about the actual chronology of publication, I would have immediately said Elantris felt much more like a first book than Warbreaker did. (In fact Elantris is a first book, and Warbreaker's a much more recent one.) The characters in Elantris are more unidimensional, the magical system is somewhat less complex (perhaps disputably), and so on. So if you're looking for a richer story and characters, Warbreaker is better. But both are still good entertainment regardless: Warbreaker is just more complex and more fulfilling. I don't see an order as necessary for reading them, although I'd probably rather build up from good to better, personally, so I'd say start with Elantris and move to Warbreaker.
The Mistborn trilogy's also worth reading if you have time. And last, I have The Way of Kings on my shelf waiting to be read, but I haven't started it yet.
Regarding style, do note that the style of The Gathering Storm and Towers of Midnight are a hybrid of Jordan's and Sanderson's styles. Once you get into either book you lose yourself in the story quite readily and forget that it's a mixture of two styles, so don't worry about Sanderson overpowering Jordan. That said, sometimes it's "obvious" (although Sanderson has said guesses about who wrote what are sometimes completely wrong) that an action-heavy, dialogue-heavy section is just too fast-paced and punchy to be anyone but Sanderson. And that's a good thing! While I'd prefer just a touch more of Jordan's deliberateness in the books, I much appreciate knowing there are no fifty-page bath scenes to get through, and that development never really slows throughout each book. :-) It's also nice to get books with only around a year's lag in between. Sanderson's a machine compared to Jordan.
Brandon himself actually recommends Warbreaker as a good introduction to his work. You can download it for free from his website, where you can also find links to his short stories, novellas, and free sample chapters from his other books.
The simple answer to your question is: you can read Brandon's books in whichever order you want (I'm grouping the Mistborn trilogy together here), though many fans recommend saving Way of Kings until last.
The long answer is: the books are interrelated, but you don't have to know that or care about it to understand the story of the books themselves. They take place in a universe known as the cosmere, a galaxy that was once the home to Adonalsium, the power of creation. Adonalsium, however, was shattered into sixteen Shards, which settled on the various worlds of the cosmere (known by fans as Shardworlds), and became the source of life and magic on those planets.
Observant readers might have noticed that one specific character has appeared seemingly in several books. Yes, this is the same exact character, and he is our introduction to the story of the cosmere. The Mistborn trilogy gives us more clues, with the Way of Kings having the most references so far to this meta-plotline.