Rebuild index in table with many values
First thing you should do is Apply SQL Server 2008 R2 SP3 ASAP. This is because SQL Server 2008 R2 RTM version is not supported at all by Microsoft. There are lots of fixes which have been included in this Service pack release and that would surely benefit SQL Server query performance. 


  You asked, So rebuild all indexes is good idea ? 


NO IT IS NOT. One should only rebuild index which is fragmented above certain value. Probably widely used value is, if index fragmentation is >30 you should go for rebuild and it is in between 10 and 30 you should go for reorganize. Please note you have standard edition so index rebuild would not be online. If you rebuild index blindly it would cause more downtime and produce more logs and thus more overhead on system. If you have narrow maintenance window you need to be highly selective with index rebuild and all this can be taken care if you go for Ola Hallengren Index rebuild solution

Other thing to note is if page_count for index, page_count can be seen from  be seen from sys.dm_db_index_physical_stats , is less than 1000 you don't need to rebuild such indexes. The reason is since page count is less pages allocated to index would be from mixed extent and these mixed pages can be lying anywhere and hence producing Logical fragmentation even after rebuild. But rest assured such small page count indexes would not affect query performance at all. You can read more about why such indexes still remain fragmented even after rebuil here

There are various options you can choose with index rebuild you can see more details here. Lot depends on your environment and configuration

You can read more about query plans from This Article. You should focus more on actual query plan than estimated query plan. Actual would tell you what exactly SQL Server is doing and what resources it is using.

You can also try SQL Sentry Plan explorer tool to get better insight into SQL Server execution plan