I feel that two Fighters, one Black Mage and one White Mage is easier, since you can pull black magic and white magic on the same turn. That's just my opinion though. You still won't really have much difficulty with three Fighters and one Red Mage.
That's a good attitude to have when playing older FF games. It's silly to expect an in-depth story with game length and gameplay rivaling less dated works such as FF IX, Chrono Cross, FFT, etc. With that in mind, we actually are able to appreciate how much they were able to create considering the limitations of the NES [I think when you play through FF II, you'll be quite impressed at what they were able to pack into that primitive little NES cartridge].
As for Elfland, that's my favourite part of the game. I love elves!
And this is true by the standards of most people that have played these games, but I don't think it's very fair to compare it to FF I. Of course they are for the same console, but let's not forget that FF I was there very first attempt at this, and they were quite new to it all at the time.