Deca-dence feels like something between Gargantia and Regios

Not as carefree (or as detailed in design/style/background with the art) as Gargantia, and while it has mystery going on, it isn't as convoluted or incomprehensible as Regios', which is kind of a nice balance.

Main characters are both likeable.