I'm a big fan of regular 1:1 meetings (both having them with my direct reports and with my own manager) and from my perspective it's perfectly fine to ask your new manager if he or she would like to schedule 1:1 meetings with you (although he or she should really be on that already, but let's give them the benefit of the doubt that they're just settling in to their position). Your manager could always say no, which would certainly tell you something about your manager and his or her management style, but there's no harm in asking. Should the manager initiate it? Yes, I would expect that. But, if they don't, and you really want the opportunity to speak on a regular basis, you should say so.
When you ask for a standing meeting, it's important to show that you have a reason for it, which gets to the second part of your question. Absent a "formal" structure for the 1:1, but with the goal of providing some sort of agenda so as not to waste anyone's time (yours or your manager's), you could follow the general organization of the daily stand-up meeting used by practitioners of Agile: what did you do yesterday, what are you working on today, what blockers do you have in front of you.
Of course, such detail is not really appropriate for a weekly or bi-weekly 1:1 with your manager, but you certainly could provide an overview of what you did since the last time you talked, talk generally about what's in front of you, and then talk about any issues or concerns that you have. All of that would start what should be an organic conversation between you and your manager; if you do 1:1s regularly you'll probably find your own way into a conversational structure that works for both of you and provides good and useful information.
On a related note, Rands talks about 1:1s from a manager's point of view, and how they're the chance for a manager to listen for updates, vents, (and possibly head off) disasters. All of that assumes a regular and useful semi-structured conversation in which you can both speak honestly, and again, from a manager's perspective (although not your manager), going to your manager and asking to implement something like that to foster a good working relationship is a good thing.