Hmm... I dunno about all of the problems being timing issues. I have never been able to pass the instr_timing test, even though I'm 99% certain I'm doing it right

Last time I checked, I failed that test, but all of the above games work just fine. About each game in particular...
Pokemon Blue - May be related to STAT interrupts. I would imagine that one type of interrupt (likely H-Blank) is being triggered so the game can safely modify SCX for the scanline for the wave-like effects. Seems like all the GB Pokemon games (Red through Crystal) don't make the very first scanline move when attacks make those wave-like effects (LY=LYC test maybe? Perhaps the effect just couldn't be done when testing for LY=0). If it loops forever rather than crashing, it's usually a sign that you're not feeding it input it expects (an interrupt, a certain value in the MMIO registers, stuff like that). The best thing to do is look at the GB assembly in a debugger and compare it in an emulator. Time consuming, but effective, since eventually your emulator will diverge from a correct, working emulator and you can then pinpoint where exactly.
Zelda - No crashes, so it's most likely an MMU issue or LCD issue. Looks like the Tile Map is getting messed up, but obviously the game logic still knows where things like the houses would be (since Link still bumps into the house, even though it's glitched). As for the stuttering in the intro, that definitely looks like a timing issue, or at least you might not be accounting for SCX properly before drawing a scanline. As I said earlier, the intro changes SCX a lot. But I would find that strange since Pokemon uses the same SCX trick and your emulator ran that just fine. Double-check it to be sure though.
Oracle of Ages - Yeah, the Oracle games need a lot of attention to HDMAs (it doesn't use General HDMA, from what I know, just HDMAs during H-Blank). This link is really helpful, and actually explains more about HDMAs than Nintendo did themselves:
http://gbdev.gg8.se/wiki/articles/Video_Display#LCD_VRAM_DMA_Transfers_.28CGB_only.29
As for double-speed, I kinda struggled to implement it correctly too, in fact, I only knew my implementation was broken because the Oracle games were messed up. I solved it by simply halving the CPU cycles the LCD acknowledged after each instruction (my emulated APU is not cycle-based, not yet), but by sending the original amount of CPU cycles to the timers. The CPU runs at 2x its normal operating speed (meaning all timers run twice as fast too) but LCD operations, DMA transfers run at the same speed. The setup I just described follows that, but it took me a while to figure it out.
Pokemon Crystal - Yeah, most likely an HDMA issue. Until I fixed my implementation of the HDMA, I had graphical issues like that in Crystal. This game makes extensive use of H-Blank HDMAs (it may occasionally use a General HDMA, but I don't specifically remember seeing that called). Probably not the source of your issue, but always make sure to use the correct VRAM bank when reading/writing. That was a source of frustration for me, briefly though.
Other stuff - Sprite palettes in DMG games are off. You may know how to fix it already, but just make sure you're correctly reading OBP0 and OBP1. Also, seems like you still have BG/Sprite priority issues (Suicune in the intro of Crystal should be behind the grass). For reference, there are only 4 cases where a sprite's pixel will prevail over the BG's pixel (GBC only):
1: BG Priority is 0 - Sprite Priority is 0 - Sprite Color is 1-3
2: BG Priority is 0 - BG Color is 0 - Sprite Priority is 1 - Sprite Color is 1-3
3: BG Priority is 1 - BG Color is 0 - Sprite Color is 1-3 (Sprite priority doesn't matter here)
4: Bit 0 of LCDC (0xFF40) is 0 - Sprite Color is 1-3
Hope this helps. I'm still working on one test ROM at the moment. The DMG bootrom, unfortunately, leaves some uncleared entries in Tile Map 0. Not too much to worry about, but it is more effort on my part to clean it up. I'll probably post at least two test online this weekend if you guys want to try them out for yourselves (and yes, they will be verified against real hardware, one already is).