Hi there soldieress
I have been asked by admin to reply to your post, so here I am First of all, please refer to my post, which explains how I have found success in just making myself feel more healthy - and lost a considerable amount of weight into the bargain by following Mark Sisson's 'Primal Blueprint', which is a less extreme version of the paleo diet you refer to. As I said in my post, I would refer you to marksdailyapple.com for lots of info about the lifestyle - yes, it is very American but anyone with a mind to can take the extremely sound principles behind the programme, based on extensive research and scientific facts and make the whole thing work to their advantage.
My first step was to read the book 'The Primal Blueprint', which is available on amazon. I was extremely sceptical that it would work - after years of low fat eating and 'chronic cardio', I have had to re-train my brain and be open to what - to me at least - is a totally different way of looking at what is healthy and what is not. Once you have read the book, I would take a good old look at the marksdailyapple website - have a marvel at the success stories, look at the archive stories and the advice given and have a serious think about why you shouldn't give it a go. I committed myself to giving it a try for 30 days and I'm unbelievably glad I did. Chris Kresser's website contains a lot of relevant and interesting articles and information but is generally a little stuffy and technical for me. Mark Sisson is a shining example of practising what he preaches and can be very amusing.
The recipe books I have bought are The Primal Blueprint Cookbook by the afore-mentioned Mark Sisson and Jennifer Meier (a bit simple if you're already a moderately capable cook and very American); The Paleo Diet Cookbook by Loren Cordain (again, very American, but more interesting and tasty-sounding recipes) and . . . wait for it . . . Paleo/Caveman Diet and Gluten Free Recipes Tailored for British Tastes Using Foods Commonly Available In English Stores and Supermarkets!!! (highly inaccurate at times, but gives you some ideas). The most interesting and tasty recipes I have found have come from links on a great website called Primal Britain, run by a young English couple who follow the Paleo/Primal principles.
Now as for whether it's worth the 'inconvenience and sacrifice' you refer to . . . I would say give it your all for a month and if you don't lose weight and feel better, I'll eat my hat!!
Hope this helps