I agree that the graphics are nice and the gameplay works for the most part, but the characters really don't work (for me!!). I was a bit embarrassed to play it at work, since other people could see my screen, haha.
Regarding not having the budget or time to do cutscenes to do "character introductions", what about posing the models and then doing paintovers, so you have narrated/written storyboards? Like that other game I can't think of right now.