If you're planning to build a standalone circuit (no Arduino board, just the AVR chip and whatever support circuitry you need), cost of the chip is barely a factor. It's in the $1 to $6 range or so, depending on which IC you use. I.e., about as much concern as the IR LED's cost.
The ATtiny85 is a good place to start for small AVR projects. It should have enough pins for you if you just want one IR receiver, and to control a couple relays. $1.30 at Digikey for qty 1. That gives you 8K of flash and 512B of RAM, which should be enough for this. It can also use its own internal 8MHz oscillator, which can be scaled down to 1MHz via the clock divider.
WRT clock speed, whatever you read isn't quite accurate. Decreasing the power supply voltage does not decrease clock speed, but running at lower voltages usually means you need more conservative clock speeds for stable operation. I.e., you can run up to 20MHz at 5v, but if you run it at 3.3v, it might not be stable at any higher than 16MHz for e.g. There's a chart of recommended Vcc vs. clock frequency in the data sheet, but many members here successfully overclock them -- it's luck of the draw. Atmel only guarantees stable operation per the chart.
Running at higher clock speeds consumes more current though. So running at lower speeds will save battery life. You'll also want to use sleep modes, so the clock is not running at all when it doesn't need to. You then use various interrupts to wake it back up -- things like timer events, input high, input low, input edge detection, that sort of thing.
The IR receiver itself will need to run at all times, so check its current consumption specs for an idea of battery drain. Relays will be a huge energy suck, so if you can use a latching relay, that helps. With those, when you trigger it on or off, it stays that way without having to apply constant magnetizing current through the coil.
Finally -- program size. Compiling for a different MCU will give you an idea, but it's not exact. For one, it depends on whether your final project will be based on Arduino libraries, or if you use vanilla AVR C/C++. The Arduino libraries take a lot of space, but they make development easier. The ATtiny85 isn't natively supported by Arduino, but you can graft that support in with user-contributed libraries. (I think it's called TinyCore, but I've never used it myself.)
If you do use Arduino libs, they have lots of device-specific includes, so code size will naturally vary somewhat by device. GCC will optimize the compiled code to include only the functions used by your code, so the fewer library calls you make (and the fewer features supported by the AVR you choose), the less needs to be included in the compiled file. By using vanilla AVR, you'll be able to shrink your code footprint way down, but at the cost of convenience. With 8K of flash on the ATtiny85, you probably won't have to worry much about code efficiency.
Thanks for your detailed comment, I learned alot. I'll go with the ATTiny85, and I'm sure the available RAM/Program memory would be enough.
Thanks. I'm familliar with IR sending/recieving in Arduino, so the program is my last problem here. But I'll remember this link for future reference.
I'd use a Tiny85 - they're more common (therefore better supported). You can probably find an IR library for it with a couple of minutes googling.
If you want to run off a button battery you'll need a Tiny85V (low power version). Make sure your IR sensor will work at that voltage though.
The biggest power drain will be the IR sensor. You may be able to power it from an I/O pin and power it on/off to save battery.
Yes, I decided to go with the 85 version, it looks like the most popular one of the Tiny series, which means there are many tutorials for it online.
So, what's the difference between the 85 to the 85V version? Only the lower minimal operating voltage of the 85V version (Which is 1.8v, comparing to the 2.7v of the 85). What are the current differences? (I don't see any in the datasheet).
My IR recievers have a 2.7v minimal operating voltage, and the current is usually below 1mA. I guess I'll use 2 AA batteries, if they can fit, for a smaller button battery if the AAs won't fit. Or should I use a higher voltage?