Emulator used: VBA re-recording v17. Make sure to set the frame skip to 0 (choose "Options->Speed->Frame Skip->skip 0"), otherwise the scrolling will be much choppier than it should be.
This is a no-emerald, Sonic-only run of Sonic Advance 2. It aims for fastest in-game times, then fastest real-time.
Here are the in-game times achieved:
Level/BossTimeTSC record
Leaf Forest 10:24:270:29:75
Leaf Forest 20:23:700:31:97
Egg Hammer Tank II0:05:620:06:70
Hot Crater 10:31:630:39:22
Hot Crater 20:34:150:46:33
Egg Bomber Tank0:06:920:12:22
Music Plant 10:33:850:47:85
Music Plant 20:40:920:55:55
Egg Totem0:05:500:05:57
Ice Paradise 10:41:950:53:68
Ice Paradise 20:32:850:45:12
Aero Egg0:05:500:05:50
Sky Canyon 10:39:730:49:28
Sky Canyon 20:37:650:53:07
Egg Saucer0:07:320:19:77
Techno Base 10:59:321:24:88
Techno Base 20:32:530:40:83
Egg-Go-Round0:06:480:10:22
Egg Utopia 10:52:481:18:35
Egg Utopia 20:56:721:15:83
Egg Frog0:08:520:12:78
XX Zone0:49:421:33:83
Total in-game time: 10:37:03 (or without bosses, 9:01:75)
This is probably the fastest Sonic game ever made, or at least it was intended to be. I was able to make Sonic move faster than the camera can keep up a decent number of times, which is pretty fast considering that the camera moves at the rate of 4 screenfuls per second. The levels are gigantic, though, which is why there aren't any sub-20-seconds level times. Finding paths through the levels was the most difficult part of making this, because there are quite a lot of alternate paths through the levels and it's not at all obvious (nor is it documented anywhere) what the fastest routes are.
Sonic has more moves here than in most Sonic games: Run, jump, crouch/spin, spin dash, air dash, slide kick, double-spin attack, homing attack, bound, and 4 mid-air tricks. Most of them turned out to be useful at least in some situations, but generally I just used run, jump, and air dash. I'll describe how the moves work to give a better idea of the game's physics and why I did certain things in this run:

Moves:

Spin Dash: Although it only takes 2 frames to perform a full-strength spin dash in this game (or 4 frames if you're already running), I only use the spin dash on those rare occasions where I need to accelerate from a very low speed, because the spin dash is too slow to be worth using in most other situations (especially because it requires leaving boost mode to perform). It's quite useful on some of the bosses, however.
Bound: This makes Sonic instantly come to a complete stop and slowly bounce downward. It would be completely useless in this run, except for what is probably a glitch that lets you skip the "slowly bounce downward" part if you activate the bound close enough to the ground after jumping. In other words, this is the move I use to get into spin dashes so quickly and completely stop or attach to platforms in boss fights.
Running and Boost Mode: "Boost Mode" is when Sonic gets these blue afterimages trailing behind him. It increases his maximum running and jumping speeds (except for post-air-dash, which is already unlimited) and allows him to jump further/higher. Sonic can enter boost mode by doing nothing but running along the ground for long enough, and it takes longer the fewer rings you have, but luckily there's a faster way to enter boost mode, which is to simply hit a booster object in the level (certain springs also work). I usually do that to enter boost mode, then maintain boost mode throughout the level by never allowing Sonic to drop below a certain speed while on the ground.
Air Dash: The air dash works like this: If a direction is double-tapped while in mid-air from a normal jump, Sonic gets a small boost of speed in the direction tapped, his vertical speed is reset, air drag stops affecting him until he lands, and he stops spinning which makes him completely vulnerable to damage from touching enemies/bosses until landing. Since it increases his speed and stops his speed from decreasing, and there is apparently no maximum speed, I abuse this move a lot to reach speeds much faster than intended.
Rolling: Rolling is the fastest way to move when Sonic is not in boost mode and there is a downhill slope. (Rolling is also basically the only way to go through an item monitor without being forced to bounce into the air.) The slope has to be really steep to be worth rolling down when already in boost mode, because the primary benefit of rolling down a slope is that the speed maximum is much higher than non-boost-mode running allows.
Slide kick: A slow move and a pretty ineffective attack in most situations, I only use this once in a level and once on a boss.
Double spin: This is when a bright blue slash/shield thing briefly circles Sonic, which can be done during any normal jump. It took me a little while to figure out what this really does. It increases the effective radius of Sonic's ball, letting him hit bosses or get nudged by corners slightly earlier than would happen otherwise.
Mid-air tricks: After getting launched into the air by almost anything in the level (springs, ramps, rails, etc.), Air dash doesn't work, but any of the 4 mid-air tricks can be used to break out of the normal trajectory. The side-spin trick is the default one I use, since it sets your speed high compared to the other tricks, although it has a longer delay. The back-flip trick is useful a couple of times for its very short delay and height gain. I avoided the other two mid-air tricks as much as possible. Note that for some things (such as windmills, bumpers, and spirals), both air dash and mid-air tricks are disabled, and for some ramps and springs it's faster to not use any tricks to maintain velocity, in case you're wondering why I sometimes wait until landing normally.
Jumping: Sonic tends to move slower in the air than on land, so I stay in the air in curled-up jumping form as little as possible. The angle of the ground greatly affects the jump - you can barely jump up at all when on a downhill slope, and uphill slopes let you jump very high into the air. Also, there is a subtle bug where the angle of the ground you previously jumped from is used instead of the current ground angle if you jump immediately after landing on a rail from an air dash, which I use for a few odd jumps. One more trick to the jumping is that jumping out of water gives you a boost upward, which when combined with being on an uphill slope and being in boost mode is how I'm able to make that insanely high jump out of the water in 1-1. Sometimes Sonic uncurls from the ball when jumping and near the ground, for instance during the first boss fight, but this is only a graphical flourish and he can still damage enemies normally in this form.
Speed shoes actually don't make much difference given the high speeds already possible. They basically only increase horizontal jumping movement and decrease the time required to enter boost mode, so I don't get them unless they're directly in the way.

Level notes:

What I do at the end of Techno Base 2 should be impossible. There's nowhere near enough room on that platform with the spikes to do 2 air dashes at such high speed and still jump clear of the spikes, and the jump onto the platform is done unusually fast. It took a lot of fiddling to get the positions right so that Sonic would just barely hit the ceiling before the platform so he'd reach it faster, and so that the slope angle bug mentioned above happened to allow for a shorter air dash than usual, and so that the collision detection conveniently failed while passing upward through the spikes. (I also pass through spikes in a few other situations, such as in Music Plant 1.)
It shouldn't be possible to retain boost mode going by those diagonally sliding platforms in Egg Utopia, but if the air dash happens at the exact frame that I'd land on the platform, for some reason boost mode doesn't go away. (It looks like I clear those platform but I actually touch them for an instant.)
Those sliding sled things in Egg Utopia normally remove boost mode and throw you uncontrollably forward, but if you land on the very back of one it doesn't remove boost mode while still propelling you forward, and if you jump at exactly the right frame the uncontrollable toss becomes a fully-controllable extra-height jump.
It's hard to notice, but I had to slow down a bit more than I would have in the Hot Crater levels, otherwise I'd fly straight through a wall to my doom. Similarly, I had to slow down at one point in Egg Utopia 1 to avoid skipping a gravity change event and getting stuck upside-down where I'm not supposed to be. Also, if you look closely you might notice that I sometimes go straight through special rings and things without picking them up when I'm too far offscreen for them to be loaded yet.
Final Boss: This is the only place in the game where I take a hit to save time. One thing that really stands out is this: If I had gotten to that ring 1 frame later, it would have disappeared; I picked it up at the last possible moment (it just happened to work out that way).

Making this:

This was made using mainly the "frame advance" and "frame search" features, both of which were very useful for frame-precise optimizations (which needed to be done everywhere).
The videos at the Sonic Center were helpful for getting a general idea of things, but didn't cover enough levels well enough to help much with route planning.
Thanks go to NintenDan for encouraging the run and helping out with routes of some earlier levels, and also for having some amazing record times at TSC to compare against.
I've redone act 1-1 at least 6 times, and all of the other levels between 2 and 4 times. The first few attempts of 1-1, made with frame advance and (I though) frame-perfect movement, were still many seconds slower than NintenDan's record time of that level. Every time I went through it I found some new trick or route change to get closer, then finally surpass that time, and only after going through all of the other levels and then starting over and redoing 1-1 yet again did I know enough of how the game's mechanics work to be able to get the times as low as this.