I personally love some of Mayakovsky's poems. He was a hooligan, an experimentalist. He was untamed and passionate about what he was doing, and you literally can see his time in his poetry. Even his ridiculous poem about Soviet passport, that caused a lot of salty jokes, is.. kinda cool. "I pull out of my wide trousers a duplicate of a priceless cargo... "

But one of my favourite Russian poets is Gumilev. His poems are pure magic: love and death, bright colours and moonlit lights, exotic countries and shamans, beautiful women and conquistadors.. I recommend him to anyone, who's a romantic (I'm not, but even I was enchanted). He also had an interesting, but tragic life.

Here are a few of his poems in English (not his best, though):
http://www.poetryloverspage.com/yevgeny/gumilev/
And a huge collection of his poems in Russian. Try them on random, maybe you'll like something:
http://gumilev.ru/verses/line/all/

I think his poems are rather easy to understand for a Russian learner. Just an example:

Сон. Утренняя болтовня

Вы сегодня так красивы,
Что вы видели во сне?
— Берег, ивы при луне..

А еще? К ночному склону
Не приходят, не любя.
— Дездемону и себя..

Вы глядите так несмело:
Кто там был за купой ив?
— Был Отелло, он красив..

Был ли он вас двух достоин?
Был ли он как лунный свет?
— Да, он воин и поэт.

О какой же пел он ныне
Неоткрытой красоте?
— О пустыне и мечте.

И вы слушали влюбленно,
Нежной грусти не тая?
— Дездемона, но не я. —

These ones are nice and easy too:
Принцесса
Отравленный

Tell me what you think of him, if you decide to try it, Johanna.