1. The cutscene > hallway > cutscene problem isn't really a problem that they couldn't fix. There are several ways around it (even with the story) such as using save stations as a hub for mini games and side quests. One example is a Save Station could also act as a way teleport to a town. The group somehow obtains an ability to disguise themselves.
Instead of multiple towns, they could do one big town with mini games, side quests, monster arena, etc.
Also the game being a "movie" is kind of standard for most FF games. Most FF had a ton of dialogue and scenes. IMO I think the problem is lack of customization options and battle system being boring at times.
(A comparison) In a sense, FFT had no towns (it's just a menu) or no exploration (okay it did near the end of the game but so did FFXIII!!!1). It was kind of linear too (exploration and storywise). Most of the gameplay came from grinding.
If FFXIII had better gameplay, then I'm sure people would have been okay with it being linear (at least how you move from place to place).
2. Battle system. One major complaint is that the fights get more and more tedious later on (and you can't outgrind it). Regular fights could last 1-3 minutes on average + they don't give crazy rewards or loot (ooo I got CP which I already capped and 50 gil worth of items! Woot!). This is unlike other FFs where after a long fight, you're usually at least rewarded (not counting FF8).
This actually diminishes one of the biggest appeals of RPGs - The reward for grinding. In FFXIII, the grind:reward ratio is really low compared to other FF games (well except maybe FFXII which was grindy as well if you didn't know what to do).
Also the game needed more customization options (just unlock all roles from the beginning, add the ability to upgrade abilities, etc), harder boss fights and easier regular fights. Since the battle system doesn't affect the story or anything, a lot could have been improved or changed.
3. Some story things need to be explained better.... unless they're intentionally saving it for a sequel or so.