Finding list of installed apps on iphone

Not from the device. However, from the desktop you could peek into the iTunes library.

There are ways to do this without a jailbroken device and not get your app rejected.
1. get a list of currently running processes see this SO answer. You will need to translate from process name to app name.
2. Check to see if any apps have registered a unique URL scheme with UIApplicationDelegate canOpenURL. There are a few sites cataloging known url schemes, this is the best one.

If an app is not currently running and does not register a custom url scheme then it will not be detected by these methods. I am interested in hearing a method that will be allowed in the app store that works better than this.

Yes it is possible to get list of all installed app

-(void) allInstalledApp
{    
    NSDictionary *cacheDict;

    NSDictionary *user;

    static NSString *const cacheFileName = @"com.apple.mobile.installation.plist";

    NSString *relativeCachePath = [[@"Library" stringByAppendingPathComponent: @"Caches"] stringByAppendingPathComponent: cacheFileName];

    NSString *path = [[NSHomeDirectory() stringByAppendingPathComponent: @"../.."] stringByAppendingPathComponent: relativeCachePath];

    cacheDict    = [NSDictionary dictionaryWithContentsOfFile: path];

    user = [cacheDict objectForKey: @"User"];

    NSDictionary *systemApp=[cacheDict objectForKey:@"System"];
}   

systemApp Dictionary contains the list of all system related app and user Dictionary contains other app information.

No, on iOS applications has no access to information of/about other applications due to sandboxed environment.