Client Profiles

Do they clients ever need to log in? If so, I would make them users and give them a custom role. Then add all the meta to the user profile page for that user only. In that case, see: http://codex.wordpress.org/Roles_and_Capabilities

If not, I would make them custom post types and use something like Scribu’s Posts-to-Posts plugin: https://github.com/scribu/wp-posts-to-posts, to relate that post type to the (non-client) users.

Does it need to be a plugin? Depends on how modular you want it. It could all exist as part of the theme. If this needs to be repeated on more sites easily, writing your own plugin is a good idea. Otherwise I would just edit the theme, personally, and then you are free to lean on other plugins for some of the lifting, such as the one I mentioned above.