Thanks for the advice, and I agree that the Duemilanove is pretty awesome (especially the shields, although from the circuit diagrams I've found that I can make most of the shields work on breadboard-format without much fuss), but nonetheless, the easiness of quickly prototyping on a breadboard is great (and the protoshields breadboard is pretty small). I think that I'm going to go with a USB Boarduino, or possible a Sanguino, after reading quite a lot of good things about them, and since they too would accomplish my breadboard needs.
Although, I'm still not a hundred percent sure, I'll have to think about it a bit more. And the USD-AUD exchange rate as it is at the moment, I'm not sure whether I'd be able to afford a Duemilanove (around $75-85 Aus including shipping).
Thanks again for the advice 