think the major difference is that Naked City is all about improvisation - even in a 2 second jump cut, the band is improvising, whereas in Fantomas it is always pretty worked out what is going to happen.
I'm not sure what the percentage of improvisation in NCs music was, but thinking of the hardcore short tracks, I wouldn't say it's too high either.
Though you have to consider "Inside Straight" or any of the Patton covers that NC was known to do live and you will see much improv. I'm thinking of the Frisell solos on "Inside Straight" and "The Way I Feel" from the 1989 Live at the Knit disc; or Zorn on "Chinatown"... But you are right about the shorts: completely composed. Even Batman, Latin Quarter, etc among the longer pieces sound to be completely composed; which blows me away that they could still play them so tightly this summer after, from what Zorn said, very little rehearsal. Whether composed or improvised NC was still amazing. Zach