it depends on what you mean by "low cost". I could help you alot more if I knew your budget.
You can get several PICs like the 12F50X for under a buck but none of them have 4K of flash rom. The closest is the 16F688 which is a 14 pin chip with 4K words of flash - about $2 for 1. To get to 8K, you have to go to a larger package and larger cost. Also, the PIC is pretty clumsy when dealing with data in program memory - I assume that's what you want the memory for.
I think the 8 pin Z8 encores have a lot of program memory but, iirc, run about $3. Nice chip, mediocre dev envt. IMHO...
The AVRs are a reasonable choice. The Atiny85 has 8K of flash in an 8 pin package but is around $2.75 q1. but... I'm not sure it's available yet. the 4K version the Atiny45 is at around $2.00