Advance Wars 2- Turn based strategy game that's easy to pick up, but incredibly deep. There was a time when I was addicted to it and ran around here shouting how that game is better than Civ. Still is.
Fire Emblem- Strategy RPG, similar to Advance Wars in many aspects. Very deep storyline and character development, but not as much strategy. I personally enjoyed this even more than Advance Wars 2.
The Legend of Zelda: A Link to the Past
The Legend of Zelda: The Minish Cap
Zelda is always good. LttP is a remake of the old SNES classic, while Minish Cap is a rather short yet extremely fun new addition to the series.
Mario&Luigi: Superstar Saga- Hillarious game. Turn-based RPG although there are a lot of action elements.
Metroid Fusion
Metroid: Zero Mission
Fusion was my first GBA game, as well as my first ever Metroid game. Highly recommended. Zero Mission I enjoyed not as much, and it's extremely short. Older fans of Metroid will like Zero Mission more, though.
Golden Sun
Golden Sun: The Lost Age
Never played them, myself, but I have heard some good things about them. Traditional turn-based RPGs, I think.
I'm not sure how many of these games he'll find in Russia, and how many of these he's willing to buy. Definitely go for Advance Wars 2 and Fire Emblem, though.