Dan of Dan's Data just posted an article about science-fiction-y batteries. He discusses a battery based on matter and antimatter but dismisses it as inconvenient (in that the energy comes out as a shower of high-energy radiation). Instead he suggests a battery based on just cramming a lot of electrons - several grams of electrons! - into a AAA-sized package, and finds that this actually stores vastly more energy. There's an error there, but it's an interesting one.
First of all let's do his calculation a little more carefully. Let's suppose we're taking 11.5 grams of electrons - roughly two billion coulombs - and cramming them into a AAA-sized package. For simplicity, let's assume the package is a conductive sphere of radius 1 cm. This is actually a capacitor, with capacitance about 1 picofarad (incidentally, 1 pf is a fairly normal size for a capacitor, though they don't usually choose a conductive-sphere form factor). So the energy stored in this capacitor is (1/2) Q^2/C, or a staggering 2*10^30 Joules, the sun's total luminosity for a couple of hours.
(All calculations are done with the charming frink, though of course the errors are my own.)
There's a problem with this, though. Actually, there are several, but let's tackle the most fundamental first: if I convert 2*10^30 J to mass using E=mc^2, I get about twenty billion tonnes. This isn't just a meaningless figure: the energy stored in the capacitor really does weigh this much. If it seems weird for energy to have mass, well, I have to agree, but you can actually see it by looking at the periodic table: a helium atom is basically four hydrogen atoms after you stick two of the electrons to two of the protons and squash all the nucleons together. But each hydrogen atom has a mass of 1.007825 u, while helium has a mass of 4.002602 u, rather than the 4.0313 u that you would expect. The difference in mass is the mass of the energy in the nucleus. Since in helium, that energy is negative (pulling the nucleons together rather than pushing them apart), the mass is also negative, and helium weighs less than the hydrogen that makes it. But it's the same phenomenon.
One interesting question is, where is all that mass? It turns out that there is a nice answer. The little conductive sphere is surrounded by a strong electric field. In fact Gauss' law lets us work out just how strong it is at the surface: 2*10^23 V/m. It turns out that electric fields store energy. The stronger the electric field, the higher the energy density it stores. If you add up all the energy stored in the electric field of this charged sphere, over all space, you get exactly the energy you had to put in to charge it up. In other words, the energy is stored in the electric field, strongest at the sphere but extending out to infinity. And when you have an energy density, you have a mass density. Dividing by c^2, you get a mass density for the electric field of 2*10^15 g/cm^3. All that mass is due to the electric field, mostly close to the sphere.
Incidentally, there's a neat little calculation here. We know that electrons are weird quantum-mechanical beasts whose position and velocity are unavoidably ill-determined, and in fact as ar as we can tell an electron is a point particle. But let's ignore that for a moment and try to figure out how big an electron is. We don't have much to go on, because they don't sit still, and they interact with other things without touching them. But there is one place to look: they have a mass. Suppose we pretend that an electron is a tiny conductive sphere, with no mass of its own, but with charge smoothly distributed over its surface. Then the electric field will have a mass of its own, just as with our little conductive sphere. What if we just declare that the mass of the electron is entirely due to this electric field? Well, then we can calculate a radius! The value you get is 1.4*10^-15 m, which is tiny enough (about a hundred thousand times smaller than an atom) to not be totally unreasonable. You get a slightly different answer if you assume the electron is non-conductive, but leaving aside that issue, this size is the classical electron radius: 2.8*10^-15 m. Astonishingly enough, this number comes up in various physical phenomena, for example Thomson scattering of light by an electron.
So we can't, even with some pretty impressive unobtainium, cram 11.5 grams of electrons into a AAA-sized space. But if we decide that 11.5 grams should be the total weight of the battery, including energy, how much energy can we store? Well, it turns out, just a little less than the matter-antimatter battery. Since the matter-antimatter battery turns its contents entirely into energy, there's no way to beat its storage efficiency. But the above calculation shows that the charged metal sphere is nearly as efficient. We just charge it up to a slightly less outrageous voltage of 4*10^13 V. Now we've got something as good as the antimatter battery, but that provides us with handy electrons! What more could you ask?
Well, for one thing, you need to get rid of the electrons somehow once you've used them. Otherwise your laptop will be constantly giving out static shocks. Try and drive an electric car with them and you'll be shedding kilowatts of static shocks. Not ideal. Also, speaking of static, the electric field of this metal sphere will extend out to infinity, and will be quite strong even at some distance. At the surface of the sphere, the electric field will be 4*10^15 V/m, which is 4*10^5 volts per angstrom. So the voltage difference across an atom will be on the order of a million volts, compared to the 13.6 volts it would take to pull an electron off a hydrogen atom. So this little sphere will shred all atoms that come near it. Worse, that field extends out to infinity, so that at a meter away it's still 40 volts per angstrom. This is going to be a real pain. Isn't there some way to shield it?
Well, yes. You just put a spherical shell around it with the opposite charge. Or you abandon the sphere and just set up two parallel plates with opposite charges. Now the fields of the two plates cancel out (nearly), everywhere except between the plates.
Actually, this kind of energy storage device exists, and you probably have thousands in your house: it's a capacitor. Now, granted, it doesn't store the kind of energy density Dan is talking about, since it's not made of unobtainium by aliens, but an appropriate bank of capacitors can store a very great deal of energy and deliver it very quickly.
But it doesn't sound so impressive to ask the aliens for a capacitor.
[Update: I talk more about what one can hope for from a capacitor here.]