I didn't spend much time adjusting the colors/palette here... most palettes have some room for expression and if you're sort of happy with the general colors and the atmosphere they create, then it comes down to what you do with pixel placement and figure/construction. I did reduce to under 16 colors because it saves time. I don't like to work with colors that are too similar, and I prefer the look of smaller palettes over smooth gradient stuff. More colors, more little AA dots to place, and that just makes things blurry, to my eye.



For the figure, I just erased the pants to move a foot back, and consequently, hip out. Reduced texture/folds on shirt. This allowed me to fit in some actual detail, like buttons. He could also have a stripe running down the shirt sleeve or something. I was thinking vintage navy/air force for theming. Added a gold accent near foot to suggest detail and some form of regality.

I was just going to mention the Amiga. A lot of the little games I did back then used "BOBs" - Blitter Objects. The Amiga doesn't have a tile PPU like the NES. There were drawbacks to using BOBs floating about. It makes level / collision data a bit harder to manage.

 When you're in a grid, you can know right away what is at 140, 204 (bitshifted by 4 for 16px tiles). It's could be a block, or air. Solving collisions is super easy.

When your objects do not have a simple shape and are just coordinates, they become hard to find. You might have to do something like:

Split the playfield up into a grid. In each cell, store a linked list of objects inside the cell. However, because some objects overlap into adjacent cells, we might have to check neighbour cells as well, or make sure overlapping objects are stored in the cells they spill into. Then to see if the player have collided, iterate all relevant lists and call the collision method for each object and check against player shape. This could rely on a bitmap, vectors, or perhaps a bounding box or radius check. But because the shape might be irregular, we might need to do special angle math so solve things like bounces/pushback. If we want to do an AI with pathfinding, we probably need to set up a mesh of nodes... but will the setup routine identify those barely-squeeze though cases?

For single screen games (e.g. Sierra adventures) we could use a pixel-level collision map, but for massive side-scroller game maps, it's a bit... ugly. Lemmings used brushes for the level design and a pixel level collision map, but those levels were pretty small and the lemmings were so small they probably only had one or two collision spots to check. At any rate, all this is a lot more work than using a simple grid where we absolutely know most of the facts and structures instantly.

On the Amiga, because it used Bitplanes, there were also some issues with drawing things on non-multiples of 8 or 16 I think. If a byte spilled over into the next, you (the GPU) have to read both bytes and mask your new byte onto those and write both back. If you draw on a multiple, you can just write over and forget unless you have transparency. I think... The Blitter would plop down 16 bits (pixels) regardless, in each bitplane, with a custom or global mask, or no mask. When I worked on a thing with 12px tiles a while ago I had to manually poke a special transparency bit mask somewhere in memory so the tiles didn't overdraw the next.  On a modern GPU this stuff doesn't matter, but the collision problem still needs to be solved and analog situations can be tricky to deal with.

In Aquaria and such it's all done by magic.

I ended up with a noisy turd.

Reasons:
I wanted a different brick size for the background (smaller to suggest distance), but this added extra noise. Could probably throw in more blank/flat tiles.

I didn't want to do leaf blobs for the plants, so I started dithering, thinking it might work on a TV.

Tried to keep the tile count and 4*4 layouts somewhat low, but sort of creeped away doing a few decorative tiles.

Tried to keep the original 3 palettes to the end, but had to lighten the sky to reduce noise and replace GUI palette red with brown as I used that for the lit ground tiles.



*Edited in some more flats. Plant dither still a mess.

I think Helm's 2x texture would work great in a raycasting or scale down+rotation engine, as the lack of single pixel detail would reduce noise (unlucky samples). I experimented some with down sampling (here from 5x) and rotation (and certain edge cases) back in 2004, as I was annoyed by how noisy (or blurry) rotated 1x graphics would look in most engines.

... I... went overboard.

But, the thing with yellow, skintone and purple is that they are useful together. Our minds read yellow as skintone when used on faces, and skintone as yellow when used on... bananas. It's sort of how a paper will almost always look white, outdoors, indoors or deep in the forest. The brain calibrates.

Purple is a good way to shade skintone, so if you have say, yellow, brown and purple, you can use brown to shade something like a banana, and purple to shade faces (and share the yellow for the lit areas). Now the yellow will look even more like yellow in one case and skintone in another.

Because you mentioned GBC, I went ahead and used only 3(4) colors. I don't know what I did with the hair. Derailed, I guess. It's now a cap (probably magical and talking).