Here you go, some of the first modding tools for CEA. One of them is ceaunpack, which can decompress the .maps in maps_original as well as the .s3dpaks in paks360. The other is ceapack, which can re-compress the files after you edit them (note that it's rather slow ATM, but you'll just have to accept that).
Both of them are command-line programs which require one parameter and accept another optional one. The first parameter is the path to the input file, and the optional second parameter is the path to the output file. If an output path isn't specified, then the file name will be suffixed with "_compressed" or "_decompressed" depending on which tool you used.
If you want to use them from Windows Explorer, just drag the file onto the .EXE (not run the EXE first and then drag the file on) and it will open it. Look for your file but with "_compressed" or "_decompressed" in its name when the program closes.
Hopefully this will help open some doors to figuring out the map structure. Source code is included under the GPLv2 (this means no stealing, leeches).
http://xboxchaos.com/cea/hcea_compression.zip