I was going to write a post about this, but searched first and found this.
It seems maybe I one of the few on here that enjoy this game. I played it pretty much all weekend.
As mentioned before, if it is your first time playing, start as Kiyomori (a dude, not a flute lady). It is a bit simpler.
Also, there is more to the game than just destroy all of the other generals/armies. You have to either keep Antoku from being kidnapped (playing as Kiyomori), or free Antoku (playing as Yoritomo/Yoshitsune), keep or get a special jewel (Yoritomo has it at the beginning of the game, Kiyomori has to steal it by killing Yoritomo). Then also destroy all the other opposing forces.
For the issue with having small army, combine with one of your other generals. I marched around yesterday with two groups of 4 generals. My army numbered nearly in the 600's. Then when I had them all as standby at a castle, they were up near 800 to defend the castle.
As for getting through the cities, just find the pattern, and hurry. Unless an archer or samurai is in my way, I do not worry about killing them. I just chop down the doors and run. Also, the time you have is based on how large your army attacking the castle is.
I love this game. Even when I was losing some this weekend, I was still having a great time playing. I got up off the couch and cheered when I killed Yoritomo yesterday. I had tried maybe 10 times to kill him during the horse chase. Then when I finally succeeded, it was awesome!
I feel I am about to finish the game with Kiyomori. Maybe a few more weekends. Once I do that, I may move to one of the other more challenging scenarios and see how it goes.