The longest-lasting timbers to make garden furniture out of are what are referred to as "durable" timbers, such as teak and iroko. Native oak heartwood is also classed as durable. The only problem with these is that they cost a lot of dosh. On the up side they last a long time even if not treated at all. Just remember to avoid using steel screws and bolts (stainless or brass won't stain the timber black as a result of tannin interaction).
Next best is probably to go for a resinous softwood such as cedar (including that dreadful introduction, leylandii) or pitch pine, although they will need to be knotted (patent knotting compound) and treated against attack by pinhole borers (Cuprinol or similar). Western Red Cedar from the USA/Canada is also good (this is not what most timber merchants refer to as "redwood" BTW, so check).
Personally, I'd avoid tanalised softwoods, despite what your friendly timber merchant might tell you. These are treated using a cyanic (cyanide) compound which is neither children or animal friendly. The process only treats the top 2 to 4 mm of timber so when you cross cut you need to seal the exposed (untreated) timber. You should wear gloves and dust masks when handling the stuff - even then you may end up with a rash or skin redness from contact with the stuff - and it is forbidden to burn the waste from manufacturing. Also you cannot finish (stain, etc) the timber until it has weathered a few months.