How do you approach a client/database with a performance issue?

Your outline is pretty accurate to how I'd do it too. Address the server & the physical architecture right at the start. This is seldom the source of the problem, so you should be able to quickly determine whether or not things are set up right. Fix what's wrong and don't look back.

After that... things get interesting.

I usually take one of two approaches. Approach #1, gather query metrics. You can set up a server-side trace or you can look at the DMV's like you've already mentioned. Figure out what's called most frequently, what runs the longest, what uses the most cpu, what uses the most i/o, and, which queries are on more than one of these lists. With that in hand, you can begin tuning. Gathering query metrics like this has the added benefit of showing you how the queries are called. For example, we had an app that called every query twice. It was just bad code, but if we weren't looking at a trace, we'd have just thought it was active. I've also seen instances where a lookup table is called hundreds of times from one connection because the developers didn't cache data... All this type of thing is what you can get from the trace.

The other approach, and it's pretty popular, is to look at the wait states. What are you waiting on? Where are the queues too long? Identify these locations, the associate those waits to procedures and begin to tune that way.

Finally, it's always best to talk to the business users. Where do they feel pain. Maybe you think, based on good data, that a given procedure needs to be tuned because it's called hundreds of times an hour, but the users are more acutely aware of a single report that runs once a day or something. Making them happy is as important as a more rigourous approach.

With a system already in production, mature or not, you can't really establish a baseline. The baseline is today. The trick is to not waste your time tuning stuff that's not important, either to the business, or to the overall performance metrics.

I would hope (and its a big hope) that there would be some benchmark of what normal is so that we could determine how slow it actually is, it may be that its not far off and therefore not worth investigating at the moment.
I would then look to see what had changed in the environment, new systems added to the server? Other systems going slow?
Then start to move in towards the data, are the server vital signs ok - CPU, HDD, paging etc what is using the resources, regardless of whether they are high or low.
Assuming we are still blaming SQL and our rogue system - then I look for locks, blocks, user/connection count, index frag, and then the bunch of trouble shooting scripts get pulled out of the toolbag ...