A few technical details to consider. I will assume a horizontally scrolling only game for this example and a tile is 16 x 16 pixels:
A full PAL screen in 32 colours is 320 x 256 x 5 planes = 51200 bytes of memory. To scroll sideways you need at least another column of tiles on the side which you smooth scroll onto the screen = 53760 bytes.
If you cannot guarantee your game will run every frame, you will need to double buffer everything. Another 53760 bytes gone.
If you want a parallax layer (say 2 rows of tiles) over a 5 bitplane display, you will need to mask those onto the display. 2 rows of tiles x 42 tiles x 5 planes will need to be drawn over the display whenever you scroll. eg. You scroll 2 pixels left, you will need the parallax layer shifted 1 pixel. That seems a hell of a lot of DMA time used when you add it up as you are effectively redrawing about 50% of the screen (2 rows x 5 planes)
If you decide to use a repeated sprite for the parallax layer, you face other limitations. It can only be 4 colours, or 16 if you bolt two of them together. You don't have enough DMA time left to change the sprite horizontally if you are going to repeat it across the display, so you have to have a small pattern repeated. eg. Risky Woods
If that's too much trouble, dump any parallax scrolling and then people complain that it doesn't scroll like the arcade version did!
Now you need some memory for your tileset - 2 entire screens of tiles will eat another 102,400 bytes of memory. You need your player and enemy sprites now, another say 4 screens worth would be a minimum. 204,800 bytes gone.
Add a few kb more memory for a copperlist or two (or if you are repeating sprites, you can easily use 50kb!) and you can see why it is difficult to get an entire game into 512k chip memory!
Now before anyone says you can compress all the graphics - not really. You have to either unpack them before you draw them (a problem if you have a big set of tiles), store them in a more efficient manner (eg. work out offsets for the tiles into memory so you store an offset into memory for each one), or do something very clever that I haven't thought of!
I'm not aware of any method that allows you to draw masked graphics onto the screen without having them unpacked. Masked graphics are required where you want a weird shape (eg. the player!) drawn over the display without erasing the background behind it. Also any graphics that partially obscure the player and background (eg. the trees in First Samurai, or the tables in Arabian Nights) also must be stored uncompressed and with a mask so they can be blitted onto the screen.
Plus more chip memory needed for sound! It's amazing any 512k games were made! :-)
You also obviously need some memory for the game maps, remember which tiles need to be redrawn, and the code - but that can reside in expansion memory.
I could be wrong with some of this, if you know better please yell! Now...
I just loaded Ruff'n'Tumble, and to me that does not look like it's 25fps - the scrolling really is quite bad on the eyes. Ditto games like Aladdin, Lion King or Cool Spot. Cool Spot is absolutely shocking imho. It would have been far better to dump the background layer and scroll smoothely. The screen isn't that big either, as there is a panel at the top and then borders around each edge. I am having a guess here but perhaps Cool Spot is only updating 12 frames per second?
PS: It would make a cool info section for HOL if people that know technical details about various games could write up information such as how many colours, screen size, scrolling, sprite tricks used etc... It would be very interesting stuff imho!