I have never played HOMM game and I wanted to try one out.
The only problem is that every game is rated about the same. So, should I start with the first game to understand the story better or get 2 or 3 for the refined graphics and game play?
any suggestions are appreciated

Both HOMM 2 and HOMM 3 are choices you really can't go wrong with. The original HOMM was pretty basic and nearly all of the elements of it were carried over to HOMM 2 (with some additions, refinements, and improved graphics). HOMM 3 is considered by many (myself included) to be the best of the series, although HOMM 2 has quite a few devoted proponents as well. Also, following the story isn't much of a concern, as although there is minor bit of story to the campaigns that's not why anyone plays these games. If you still have trouble deciding just flip a coin between HOMM 2 and 3, since as I mentioned you really can't go wrong with either one.

Alright, based on what you said I think I'll go with the 3rd one. Thanks for the help!

Good decision; not because it's the "better" game (which is, like DarrkPhoenix stated, quite debatable), but because it's quite a bit more beginner-friendly than HoMM2.

I agree, Heroes 3 seems to be more forgiving than Heroes 2 (which is in turn more forgiving than Heroes 1).

I sure hope that's true, because I'm managing to be no good at HoMM1. I guess I'm not used to enemy units being able to wander around my lands and reclaim my resource generators . I feel like I want to put up some base defense or something.

Try homm4. Its very interesting game, but if you try homm2 or 3 first, then you might wont like homm4 with its graphics(fog of war, and other stuff). But homm4 is definately a good game.

Another vote for 3.
2 has incredible charm. I mean the game just seems perfect and the colors and music are bright and upbeat without being cheesy and wearying. I've often described it as a perfect game.
But most people go for graphics, and 3 brings over the good parts of 2 while upgrading the graphics.

Just avoid the first one. It really aged badly. HoMM 2 is just like the first, only better. HoMM is better, but different.
Also, HoMM I has no storyline - so you don't have to play it to understand the world.

If you are worried about story just start with Homm2 its not very hard and pretty easy to get the hang of. But I personally think that Homm3 was the best of the series.

I'm gonna have to go with HOMAM 1.
It's what I did and it's very nice to see the series improve as you go.

I prefer HOMM II better because of all the settings you can give the AI. HOMM III just has one choice and all the ai play at that level. In HOMM II you could give one AI dunce and the next AI EXPERT and the next AI Normal etc. etc. You could also set them at random and then like a box of chocolates you never knew what you were going to get in the form of AI play.
Play wise yes HOMM III adds more detail and strategy to the game, but HOMM II just hits that old KISS feature games should really have (Keep it simple stupid). I also like the larger units in HOMM II it seems every iteration the units get smaller and smaller and smaller. I like to see what I'm playing while I'm playing. ;)

ravinhood: Only HoMM1 lets you change individual CPU opponents' difficulty

HoMM2, without a doubt.
The first one is a classic that deserve to be revisited by any fan of the series but graphically it's unpolished, and factions are very unbalanced.
The third one has tons of heroes, each with their own class, skills, bonus and penalty, there are hundreds of artifacts, spells, units, many which all look alike, just like the castles, just like the land tiles... Don't get me wrong, HoMM3 is clearly the main dish when it comes to the HoMM series, but it's not the entry.
IMO, the best game to get into the series and learn the basics is the second game. It's more polished and more balanced than the first game. Nearly every game elements from the third game are present in the second game, but in much smaller quantity, making things easier to learn and memorize, and with the colorful 2D graphics of the second game, units, heroes, castles and land tiles are also much easier to recognize.
Start with HoMM2 to learn how the series works, learn the basics and develop some tactics that will help you in the other games. Play a bunch of scenarios, give the main campaigns a try (but stay away from the Price Of Loyalty campaigns, they are shorter but they are also much harder) and when you feel you know enough about the game, make the jump to the HoMM3.
Story wise, there is nothing to worry about. Like DarrkPhoenix said before, the plot is not the main reason why people play these games. Decades span in between each games and their addons, each campaigns tell different stories, with different characters and locations, there's no need to play the previous games or the M&M games to have fun with HoMM games.

HoMM1 would really only be for fans of the series that want to see how it all started (well, in a way it really started with King's Bounty, but I digress). If you want to do the series, but don't have thousands of hours to play, you can skip HoMM1.
HoMM2 and HoMM3 are must have, they are both great.
HoMM4 I hated with a passion. It destroyed what makes HoMM what it is, removed the tactical importance of your army and made it all about the hero. Also, the AI was non-existant.
HoMM5 was good, though some people didn't like it as much as I did.
So, if you want to do the whole series, I would start with HoMM2, then 3, then you could skip 4, or play it, but don't expect any challenge, and then 5. Try to play the expansions, they are great.
Once you're finished (or whenever you want), you can try user-made mods. There's one for HoMM3 that pretty much changes the whole game. I recommend it. Don't know the name but you can probably Google for it as HoMM3 mods or something.