The heroes of Russian folklore:

Ivan Tsarevich - Иван-Царевич
Ivan the Fool - Иван-Дурак, Иванушка-Дурачок
Vasilisa the Beautiful/the Wise - Василиса Прекрасная/Премудрая
Alyonushka and her brother Ivanushka - Алёнушка и ее братец Ивенушка
Frog Tsarevna - Царевна-Лягушка
The Unsmiling Tsarevna - Царевна Несмеяна
Bogatyrs (Knights) - Богатыри

Objects with magical properties:

The flying carpet (ковер-самолет)
Скатерть-самобранка (A table-cloth which, when opened, sets itself magically with all kinds of yummy dishes)
Шапка-невидимка (a hat that makes you invisible when you put it on)
Сапоги-скороходы (boots which, when put on, allow you to travel great distances with just a few paces)

Magical creatures:

Жар-птица (the Firebird; a sort of phoenix)

In Slavic folklore, the Firebird (жар-птица: жар - heat, птица - bird) is a magical glowing bird from a faraway land, which is both a blessing and bringer of doom to its captor.

The Firebird is invariably described as a large bird in majestic plumage that brightly glows in red, orange and yellow light, like a bonfire that is just past the turbulent flame. The feathers do not cease glowing if removed, and one feather can light a large room if not concealed. In later iconography, the form of Firebird is usually as of a smallish peacock of fire colors, complete with a crest on its head and tail feathers with glowing "eyes".

A typical role of the Firebird in fairy tales is an object of difficult quest. The quest is usually initiated by finding a lost tail feather of the Firebird, upon which the hero sets out to find and capture the live bird, sometimes on his own accord, but usually on the bidding of a father or king. The Firebird is a marvel, highly coveted, but the hero, initially charmed by the wonder of the feather, eventually blames it for his troubles.
The Firebird tales follow the classical scheme of fairy tale, with the feather serving as a premonition of hard journey, with magical helpers met on the way, who help in travel and capture of the Bird, and returning from the faraway land with the prize. The most popular version is found in the tale of Ivan Tsarevich and the Grey Wolf.

The story of Firebird quest has inspired literary works, including "The Little Humpback Horse" by Pyotr Yershov. Composer Stravinsky achieved an early success with a large-scale ballet score, The Firebird.

The Firebird concept has parallels in the Iranian legends of magical birds, in the Brothers Grimm's fairy tale about The Golden Bird and the related Russian magical birds like Sirin. The story of the quest itself is closely paralleled by Armenian Hazaran Blbul. In the Armenian tale, however, the bird does not glow but rather makes the land bloom through its song. In the Czech folklore, it is called Pták Ohnivák (Bird Fire-like) and appears, for example, in a Karel Jaromír Erben fairy tale, also as an object of difficult quest. Moreover, in the beginning of this fairy tale, the bird steals magical golden apples belonging to a king and is therefore pursued by the king's servants in order to protect the precious apples.

The story of the firebird comes in many different forms. Some folk tales say that the Firebird is a mystical bird that flies around a king’s castle and at night swoops down and eats all the king's golden apples. Others say that the firebird is just a bird that flies around giving hope to those who need it. Some additions to that legend say that when the firebird flies around his eyes sparkle and pearls fall from his beak. The pearls would then fall to the peasants, giving them something to trade for good or services. In the most common version of the legend, a Tsar commands his three sons to capture the firebird that keeps flying down from above and eating his apples. The golden apples are in the Tsar’s orchard and give youth and strength to all who eat them. The sons end up barely missing the bird, but they catch one of his feathers that glows in the night. They take it in a dark room and it lights the room completely. The mystery of the feather has illuminated hearts of men for many years.
Ivan Bilibin's illustration to a Russian fairy tale about the Firebird, 1899.

The following are all by Viktor Vasnetsov:
Ivan Tsarevich riding the Gray Wolf

Ivan Tsarevich and the Firebird on a magic carpet
The Flying Carpet

from http://s42.radikal.ru/i097/0807/23/ad29ef66a737.jpg
Alyonushka

The Unsmiling Tsarevna (Nesmeyana)

Frog Tsarevna