You need the original data files for fheroes2, but you can buy HOMM2 Gold from GoG.com ($US9.99) which gives you them. HOMM3 Complete from GoG.com ($US9.99) and (freely downloadable) WoG files give you the files necessary to run VCMI. Of the two, I would say that fheroes2 is in the more playable state, however the AI is in the process of development and improvement. Exploring maps, especially with the new features and a tough end hero, are still a heap of fun. eg. Plains of Aekon and Clouds of Xeen are two good ones in this respect (Xeen has quite a tough end hero, and Plains of Aekon can have a few built up heroes, especially on Impossible). Impossible difficulty isn't as difficult as in original H2, but that is not necessarily *too* bad. 
Let's face it, the HOMM2 AI was very good, and the fheroes2 AI is not there yet. But it is being worked on and improved periodically, which can't be said for the original HOMM2 AI. 
And you'll find that the traditional AI exploits from H2 are not there, although there are some other ones specific to current fheroes2 AI. The fheroes2 AI can build up some quite fearsome armies which can cause some losses, although sometimes it doesn't attack when it could.
Anyway, if you can afford the $US9.99 for HOMM 2 Gold from GoG.com, then I strongly suggest giving fheroes2 a shot. In the last week there were over 400 downloads, not bad for a mod based on a game from 1996/1997. 
