Ultra low power/ simple flashing circuit
The first circuit on the page you linked to is already pretty efficient in that just about all supply current is used to light the LEDs.  So the issue isn't lower power as much as to be able to run from a lower voltage.

Typical coin cells, like the common CR2032, put out about 3V.  This mean you have to use LEDs that light at somewhat lower voltage.  Fortunately common green LEDs typcially light at around 2.1V.  Switching to green LEDs allows for using a 3V supply.

To cut down power, you have to cut down the current thru the LEDs.  This directly effects brightness.  If this device is for indoor use, even 1mA may be good enough to noticeably light the LEDs.  Getting decent LEDs with decent efficiency definitely helps here.  Let's say you want to draw only 2 mA from the coin cell.  The voltage drop accross the resistor in series with the LED will be roughly 800 mV.  800mV / 2mA = 400&Omega;.  That's a starting point.  Then you can trade off battery life with brightness from there.  Lower resistors will give higher brightness and shorter battery life.