Concerning advanced differential geometry textbooks in general:
There's a kind of a contradiction between "advanced" and "textbook". By definition, a textbook is what you read to reach an advanced level. A really advanced DG book is typically a monograph because advanced books are at the research level, which is very specialized. Anyway, these are my suggestions for DG books which are on the boundary between "textbook" and "advanced". (These are in chronological order of first editions.)
- Bishop/Crittenden, "Geometry of manifolds" (1964). Quite advanced, although not too difficult, despite the 1964 date.
- Cheeger/Ebin, "Comparison theorems in Riemannian geometry" (1975). This is on the boundary between textbook and monograph. Definitely advanced, despite the 1975 date.
- Greene/Wu, "Function theory on manifolds which possess a pole" (1979). Monograph/textbook about function theory on Cartan-Hadamard manifolds, including extensive coverage of Kähler manifolds.
- Schoen/Yau, "Lectures on Differential Geometry" (1994). This is about as advanced as it gets. You need to read at least 5 other DG books before starting this one.
- Theodore Frankel, "The geometry of physics: An introduction" (1997, 1999, 2001, 2011). This has lots of advanced DG, but in the physics applications, not so much on topological DG questions.
- Peter Petersen, "Riemannian geometry" (1998, 2006). Very definitely advanced. You need to read at least 3 other DG books before this one.
- Serge Lang, "Fundamentals of differential geometry" (1999). This is definitely advanced, although it nominally starts at the beginning. It's what I call a "higher viewpoint" on DG. Very thorough and demanding.
- Morgan/Tián, "Ricci flow and the Poincaré conjecture" (2007). Advanced monograph on the Poincaré conjecture solution, but written almost like a textbook.
- Shlomo Sternberg, "Curvature in mathematics and physics" (2012). Definitely advanced. On the boundary between DG and physics.
I would say that all of these books are beyond the John M. Lee and Do Carmo textbook level.
I've published a number of undergraduate and graduate science books, some heavy in mathematics, but no true mathematics textbooks. I've thought long and hard about how to design and craft them, and have several professional calligraphers, type designers, book designers in my immediate family, and they (and of course my students) have given lots of great feedback.
I think the first thing any author must address is "why another book?" Because writing a book is such an ordeal, you should really have the sense that you have something important and unique to say, or new viewpoints, that will energize you through the inevitable burden of writing. Much of your design decisions will stem from your (preferably) unique pedagogical views.
My personal writing style (and indeed academic/professional style) is to be as visual as possible. (Try to get your publisher to agree to full-color graphics.) Many students will remember topics better with careful graphics, find topics by flipping through the book faster, and so on. Two of my favorite math book presentations are Visual group theory by Nathan Carter and An illustrated theory of numbers by Martin Weissman, both of which should give you ideas. This latter uses a great $\LaTeX$ style sheet, which I am sure is freely available. Also, be sure to read the master--Ed Tufte--and his great books, such as Envisioning information.
Take time making great figures!! I spent a week programming a three-dimensional Voronoi tesselation (with data points), and as far as I can tell my book Pattern classification (2nd ed., 2000) was the first to have it. Likewise, I wrote the first scientific paper on auto-random-dot stereograms (remember Magic Eye?) and my book Seeing the light was the first to include one. Students remember these!
I very much like separate little sections that work a problem and integrate the material in the rest of the body of the text. You might like to put in little questions within the text—in a different color, separated—to keep the student alert and thinking.
My preference is to have bibliographical and historical material separate at the back of each chapter, not within the body of a chapter. Students don't want to learn from sentences such as: "As Jones and Smith (1988) and later Candace and Tao (2007) showed, the signal..." Don't burden the student with history and citations: The primary material is surely difficult enough.
Another issue is whether you'll teach coding, or use programming, as part of the material. If you want the broadest adoption, write pseudo-code, so students coming with different programming backgrounds can all learn. However, if you are linked to a particular language (Mathematica, Matlab, R, etc.), then post the exact code... with helpful comments.
You will likely test market your book on your students as you write. Ask for honest feedback... including feedback about the design.
Best Answer
Since the question was tagged with "algorithms", I will give an algorithms recommendation. (You don't say specifically what type of problems you want to solve, but you do mention "algorithmic complexity.") For a book that was written to motivate the theory of algorithms from real-world problems, I would recommend Algorithm Design by Kleinberg and Tardos. It discusses many problem-solving methods. From the website for the book:
Amazon link: http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358