I can chime in for them until they read this. It wouldn't be hard at all, it'd just be hard to get it working well.
Let me explain that one. The best way to do beat detection is to either open the sound file in question twice, and "read" one of them to determine the beats or to "record" the mixer channel of your pc and analize that. If you do the first one then you are limited by what you can do as it has to be a sound the app is making and only one sound at a time can be read. If you do the latter then every sound is analized, even system sounds, and thus you don't have a lot of control over it.
In either case, it requires the direct reading and manipulation of memory, not to mention reading a very large amount of data quickly and on-the-fly. Even after all of that, you have to normalize the data and convert it into something useful, which could potentially get quite complicated. Modern pcs can do this, but it eats up a lot of resources. Apps like winamp and wmp often hit 100% of the processor when a visualiztion is used and that has less to do with the rendering and more to do with beat detection. Of course when you start another app this number goes down (because the thread is of low priority) but the visualization suffers.
I've experimented with it before. It's very fun to do and you can get some decent results, I just don't know if you'd want to put it in a fe though as high-end fes need a lot of resources for timing-critical animations. I'm not so sure it'd be a good idea for mame either.