In this scenario, where you don't yet carry enough weight/experience to out-and-out declare that the index rebuilds are absolutely necessary, I suggest you utilise a test/dev environment. Take a recent copy of the database from production, run some performance testing on a typical workload, and then rebuild all indexes. If this then gives you solid evidence, you can convince others of the benefit.

If your database is from a 3rd party vendor, you can ask them if they have index maintenance recommendations and present that to the rest of your IT department.

As to the safety, the main thing to look out for is blocking other users, and running out of transaction log space (including any log shipping or replication or mirroring). Plus, the fact that you've run it in a test environment should help to remove fears. If you have room for a maintenance window, you can always suggest rebuilding certain indexes in a controlled method until you're sure of what the impact will be.

You might find that fragmentation is not the primary cause of the problems, but a lack of appropriate indexes, particularly if this is custom software, or your vendors also don't know much about index maintenance. Start tracing any queries that perform a large number of reads (start with 20,000 and work back from there).